最长回文字串 汇总

回文串就是一个正读和反读都一样的字符串，比如“level”或者“noon”等等就是回文串。回文子串，顾名思义，即字符串中满足回文性质的子串。比如输入字符串 "google”，由于该字符串里最长的对称子字符串是 "goog”，因此输出4。

1.问题解决的基本方法

分析：过判断一个字符串是不是对称的函数，这个题目可以看成是该函数的加强版。

要判断一个字符串是不是对称的，不是一件很难的事情。我们可以先得到字符串首尾两个字符，判断是不是相等（string类翻转比较很容易实现）。如果不相等，那该字符串肯定不是对称的。否则我们接着判断里面的两个字符是不是相等，以此类推。

#include

using namespace std;

//字符串是否对称

bool isAym(char *cbegin, char *cend)

{

if(cbegin == NULL || cend ==NULL || cbegin > cend)

{

return false;

}

while(cbegin

{

if(*cbegin!=*cend)

{

return false;

}

cbegin++;

cend--;

}

return true;

}

//O(n*n*n)复杂度的子字符串

int getMaxSym(char * str)

{

if(str == NULL)

return 0;

int maxlength = 0, strlength = 0;

char *pFirst = str;

char *strEnd = str + strlen(str);

while(pFirst

{

char *pLast = strEnd;

while(pLast > pFirst)

{

if(isAym(pFirst, pLast))

{

strlength = pLast - pFirst + 1;

if(strlength > maxlength)

{

maxlength = strlength;

}

}

pLast --;

}

pFirst ++;

}

return maxlength;

}

上述方法的时间效率：由于需要两重while循环，每重循环需要O（n）的时间。另外，我们在循环中调用了IsSym，每次调用也需要O（n）的时间。因此整个函数的时间效率是O（n^3）。

2、改进的解决方案

输入：abcddcba，按照上述程序，要分割成 'abcddcba’, 'bcddcb’, 'cddc’, 'dd’…等字符串，并对这些字符串分别进行判断。不难发现，很多短子字符串在长些的子字符串中比较过，这导致了大量的冗余判断，根本原因是：对字符串对称的判断是由外向里进行的。

换一种思路，从里向外来判断。也就是先判断子字符串(如dd)是不是对称的。如果它(dd)不是对称的，那么向该子字符串两端各延长一个字符得到的字符串肯定不是对称的。如果它(dd)对称，那么只需要判断它(dd)两端延长的一个字符是不是相等的，如果相等，则延长后的字符串是对称的。

/*

中心扩展

中心扩展就是把给定的字符串的每一个字母当做中心，向两边扩展，这样来找最长的子回文串。算法复杂度为O(N^2)。

但是要考虑两种情况：

1、像aba，这样长度为奇数。

2、想abba，这样长度为偶数。

*/

class Solution {

public:

string longestPalindrome(string s) {

const int length=s.size();

int maxlength=0;

int start=-1;

if(length==1)

return s;

for(int i=0;i

{

int j=i-1,k=i+1;

while(j>=0&&k

{

if(k-j+1>maxlength)

{

maxlength=k-j+1;

start=j;

}

j--;

k++;

}

}

for(int i=0;i

{

int j=i,k=i+1;

while(j>=0&&k

{

if(k-j+1>maxlength)

{

maxlength=k-j+1;

start=j;

}

j--;

k++;

}

}

if(maxlength>0)

return s.substr(start,maxlength);

else

return s.substr(0,1);

}

};

3、manacher算法

由于总共有O（n）个字符，每个字符可能延长O（n）次，每次延长时只需要O（1）就能判断出是不是对称的，因此整个函数的时间效率是O（n^2）。

上述方法称为朴素算法，关于字符串的题目常用的算法有KMP、后缀数组、AC自动机，这道题目利用扩展KMP可以解答，其时间复杂度也很快O(N*logN)。但是，这里介绍一个专门针对回文子串的算法，其时间复杂度为O(n)，这就是manacher算法。

#include

#include

using namespace std;

//预处理,将str：abba转换为: $#a#b#b#a#\0(从1开始)

/*

算法的基本思路是这样的：把原串每个字符中间用一个串中没出现过的字符分隔#开来(统一奇偶)，同时为了防止越界，在字符串的首部也加入一个特殊符$，但是与分隔符不同。同时字符串的末尾也加入'\0'。算法的核心：用辅助数组p记录以每个字符为核心的最长回文字符串半径。也就是p[i]记录了以str[i]为中心的最长回文字符串半径。p[i]最小为1，此时回文字符串就是字符串本身。

示例：原字符串 'abba’，处理后的新串 ' $#a#b#b#a#\0’，得到对应的辅助数组p=[0,1,1,2,1,2,5,2,2,1]。

*/

char * pre(char *str)

{

int length = strlen(str);

char *prestr = new char[2*length + 4];

prestr[1] = '$';

for(int i=0;i

{

prestr[2*(i+1)] = '#';

prestr[2*(i+1)+1] = str[i];

}

prestr[2*length+2]='#';

prestr[2*length+3]='\0';

return prestr;

}

//manacher算法

int getMaxSym3(char *str)

{

char *prestr = pre(str);

int mx =0, pi=1;//边界和对称中心

int len = strlen(prestr);

//辅助数组

int *p = new int[len];

p[0] = 0;

for(int i=1;i

{

{

p[i]=min(mx-i,p[2*pi-i]);//核心

}

else

{

p[i]=1;

}

while(prestr[i-p[i]]==prestr[i+p[i]]&&i-p[i]>0&&i+p[i]

{

p[i]++;

}

if(i+p[i] > mx)

{

mx = p[i] + i;

pi = i;

}

}

//最大回文字符串长度

int maxlen = 0;

pi=0;

for(int i=0;i

{

if(p[i]>maxlen)

{

maxlen = p[i];

pi=i;

}

}

char *pstr=new char[maxlen];

int i,j;

maxlen-=1;

for(i=pi-maxlen,j=0;i

if(prestr[i]!='#')

{

pstr[j]=prestr[i];

j++;

}

pstr[j]='\0';

cout

delete []prestr;

delete []p;

return maxlen ;//返回最长字串的最大值

}

int main()

{

char p[100];

while(cin>>p)

{

cout

}

return 0;

}

上面几个变量说明：pi记录具有遍历过程中最长半径的回文字符串中心字符串。mx记录了具有最长回文字符串的右边界。

pi是最长回文字符串（淡蓝色）的中心，如果以j为中心的最大回文串如上如所示，那么i处的情况与j处相同（关于pi的两侧是对称的）。这样便减少了运算量，i的对称位置是2*pi-i。

但是有另外一种情况，就是j的一部分超出蓝色部分，这时p[i]=p[j]就不一定对了，如下图

这就为什么有取最小值这个操作：

if(mx>i){ p[i]=min(mx-i,p[2*pi-i]);//核心}

剩下的代码就很容易看懂了。

最后遍历一边p数组，找出最大的p[i]-1就是所求的最长回文字符串长度，说明如下：

（1）因为p[i]记录插入分隔符之后的回文字符串半径，所以以i为中心的回文字符串长度为2*p[i]-1。例如：bb=>#b#b#，中间#的半径为3，回文字符串长度为2*3-1；

（2）注意上面两个串的关系。 #b#b#减去一个#号的长度就是原来的2倍。即((2*p[i]-1)-1)/2 = p[i]-1，得证。

4、比赛快速求解最长回文子串长度的模板

#include

#include

#include

#include

using namespace std;

const int MAX = 1000010;

char s[MAX];

char ss[MAX

int dp[MAX

int solve(int len)

{

int ans=0;

int right=-1;

int id=-1;

for(int i=0;i

{

int r=1;

if(right>=i)

r=max(r,min(right-i+1,dp[2*id-i]));

while((i-r+1>=0&&i+r-1

r++;

r--;

if(i+r-1>right)

{

right=i+r-1;

id=i;

}

dp[i]=r;

ans=r;

}

return ans-1;

}

int main()

{

while(scanf("%s",s)!=EOF)

{

int len=strlen(s);

int cnt=0;

for(int i=0;i

{

ss[cnt++]='#';

ss[cnt++]=s[i];

}

ss[cnt++]='#';

printf("%d\n",solve(cnt));

}

return 0;

}