Leetcode（5）-最长回⽂⼦串（包含动态规划以及Manacher算
法）
给定⼀个字符串 s，到 s 中最长的回⽂⼦串。你可以假设 s 的最⼤长度为1000。
⽰例 1：
输⼊: "babad"
输出: "bab"
注意: "aba"也是⼀个有效答案。
⽰例 2：
输⼊: "cbbd"
输出: "bb"
⾃⼰的思路：求⼀个字符串的最长回⽂⼦串，我们可以将以每个字符为⾸的⼦串都遍历⼀遍，判断是否为回⽂，如果是回⽂，再判断最⼤长度的回⽂⼦串。算法简单，但是算法复杂度太⾼，O（n^3）
string longestPalindrome(string s)
{
pty()) return"";
if(s.size()==1) return s;
int start=0,maxlength=1;//记录最⼤回⽂⼦串的起始位置以及长度
for(int i=0;i<s.size();i++)
for(int j=i+1;j<s.size();j++)//从当前位置的下⼀个开始算
{
int temp1,temp2;
for(temp1=i,temp2=j;temp1<temp2;temp1++,temp2--)
{
if(s[temp1]!=s[temp2])
break;
}
if(temp1>=temp2 && j-i+1>maxlength)//这⾥要注意条件为temp1>=temp2，因为如果是偶数个字符，相邻的两个经上⼀步会出现⼤于的情况
{
maxlength = j-i+1;
start=i;
}
}
return s.substr(start,maxlength);//利⽤string中的substr函数来返回相应的⼦串，第⼀个参数是起始位置，第⼆个参数是字符个数
}
很明显上述的算法复杂度太⾼，应该有更加快捷的做法来处理。下⾯介绍两种⽅法
（1）DP
动态规划的⽅法，我会在下⼀篇单独来介绍，这⾥只说明此题的DP代码
对于字符串str，假设dp[i,j]=1表⽰j]是回⽂⼦串，那个必定存在dp[i+1,j-1]=1。这样最长回⽂⼦串就能分解成⼀系列⼦问题，可以利⽤动态规划求解了。⾸先构造状态转移⽅程
上⾯的状态转移⽅程表⽰，当str[i]=str[j]时，如果str[j-1]是回⽂串，则j]也是回⽂串；如果str[j-1]不是回⽂串，则j]不是回⽂串。
初始状态
dp[i][i]=1
dp[i][i+1]=1 if str[i]==str[i+1]
上式的意义是单个字符，两个相同字符都是回⽂串。
string longestPalindrome(string s)
{
if (s.empty()) return"";
int len = s.size();
if (len == 1)return s;
int longest = 1;
int start=0;
vector<vector<int> > dp(len,vector<int>(len));
for (int i = 0; i < len; i++)
{
dp[i][i] = 1;
if(i<len-1)
{
if (s[i] == s[i + 1])
{
dp[i][i + 1] = 1;
start=i;
longest=2;
}
}
}
for (int l = 3; l <= len; l++)//⼦串长度
{
字符串长度如何定义for (int i = 0; i+l-1 < len; i++)//枚举⼦串的起始点
{
int j=l+i-1;//终点
if (s[i] == s[j] && dp[i+1][j-1]==1)
{
dp[i][j] = 1;
start=i;
longest = l;
}
}
}
return s.substr(start,longest);
}
这⾥我们需要⽤⼀个⼆维数组dp来作为备忘录，记录⼦问题的结果，以便重复的计算。这也是动态规划的精髓所在。不过这种做法的算法复杂度也是O(n^2)
（2）Manacher法
这是⼀个专门⽤作处理最长回⽂⼦串的⽅法，思想很巧妙，⽐较难以理解，这⾥直接借⽤了别⼈的讲解⽅法。其实主要思想是，把给定的字符串的每⼀个字母当做中⼼，向两边扩展，这样来最长的⼦回⽂串，这个叫中⼼扩展法，但是这个⽅法还要考虑到处理abba这种偶数个字符的回⽂串。Manacher法将所有的字符串全部变成奇数个字符。
Manacher算法原理与实现
下⾯介绍Manacher算法的原理与步骤。
⾸先，Manacher算法提供了⼀种巧妙地办法，将长度为奇数的回⽂串和长度为偶数的回⽂串⼀起考虑，具体做法是，在原字符串的每个相邻两个字符中间插⼊⼀个分隔符，同时在⾸尾也要添加⼀个分隔符，分隔符的要求是不在原串中出现，⼀般情况下可以⽤#号。下⾯举⼀个例⼦：
（1）Len数组简介与性质
Manacher算法⽤⼀个辅助数组Len[i]表⽰以字符T[i]为中⼼的最长回⽂字串的最右字符到T[i]的长度，⽐如以T[i]为中⼼的最长回⽂字串是T[l,r]，那么Len[i]=r-i+1。
对于上⾯的例⼦，可以得出Len[i]数组为:
Len数组有⼀个性质，那就是Len[i]-1就是该回⽂⼦串在原字符串S中的长度，⾄于证明，⾸先在转换得到的字符串T中，所有的回⽂字串的长度都为奇数，那么对于以T[i]为中⼼的最长回⽂字串，其长度就为2*Len[i]-1，经过观察可知，T中所有的回⽂⼦串，其中分隔符的数量⼀定⽐其他字符的数量多1，也就是有Len[i]个分隔符，剩下Len[i]-1个字符来⾃原字符串，所以该回⽂串在原字符串中的长度就为Len[i]-1。
有了这个性质，那么原问题就转化为求所有的Len[i]。下⾯介绍如何在线性时间复杂度内求出所有的Len。
（2）Len数组的计算
⾸先从左往右依次计算Len[i]，当计算Len[i]时，Len[j](0<=j<i)已经计算完毕。设P为之前计算中最长回⽂⼦串的右端点的最⼤值，并且设取得这个最⼤值的位置为po，分两种情况：
第⼀种情况：i<=P
那么到i相对于po的对称位置，设为j，那么如果Len[j]<P-i，如下图：
那么说明以j为中⼼的回⽂串⼀定在以po为中⼼的回⽂串的内部，且j和i关于位置po对称，由回⽂串的定义可知，⼀个回⽂串反过来还是⼀个回⽂串，所以以i为中⼼的回⽂串的长度⾄少和以j为中⼼的回⽂串⼀样，即Len[i]>=Len[j]。因为Len[j]<P-i，所以说i+Len[j]<P。由对称性可知Len[i]=Len[j]。
如果Len[j]>=P-i，由对称性，说明以i为中⼼的回⽂串可能会延伸到P之外，⽽⼤于P的部分我们还没有进⾏匹配，所以要从P+1位置开始⼀个⼀个进⾏匹配，直到发⽣失配，从⽽更新P和对应的po以及Len[i]。
第⼆种情况: i>P
如果i⽐P还要⼤，说明对于中点为i的回⽂串还⼀点都没有匹配，这个时候，就只能⽼⽼实实地⼀个⼀个匹配了，匹配完成后要更新P的位置和对应的po以及Len[i]。
2.时间复杂度分析
Manacher算法的时间复杂度分析和Z算法类似，因为算法只有遇到还没有匹配的位置时才进⾏匹配，已经匹配过的位置不再进⾏匹配，所以对于T字符串中的每⼀个位置，只进⾏⼀次匹配，所以Manacher算法的总体时间复杂度为O(n)，其中n为T字符串的长度，由于T的长度事实上是S的两倍，所以时间复杂度依然是线性的。
下⾯是算法的实现，注意，为了避免更新P的时候导致越界，我们在字符串T的前增加⼀个特殊字符，⽐如说‘$’，所以算法中字符串是从1开始的。、
string longestPalindrome(string s)
{
string manaStr = "$#";
for (int i=0;i<s.size();i++) //⾸先构造出新的字符串
  {
manaStr += s[i];
manaStr += '#';
}
vector<int> rd(manaStr.size(), 0);//⽤⼀个辅助数组来记录最⼤的回⽂串长度，注意这⾥记录的是新串的长度，原串的长度要减去1
int pos = 0, mx = 0;
int start = 0, maxLen = 0;
for (int i = 1; i < manaStr.size(); i++)
{
rd[i] = i < mx ? min(rd[2 * pos - i], mx - i) : 1;
while (i+rd[i]<manaStr.size() && i-rd[i]>0 && manaStr[i + rd[i]] == manaStr[i - rd[i]])//这⾥要注意数组越界的判断，源代码没有注意，release下没有报错
rd[i]++;
if (i + rd[i] > mx) //如果新计算的最右侧端点⼤于mx，则更新pos和mx      {
pos = i;
mx = i + rd[i];
}
if (rd[i] - 1 > maxLen)
    {
start = (i - rd[i]) / 2;
maxLen = rd[i] - 1;
}
}
return s.substr(start, maxLen);
}

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。