求一个字符串中的最长回文长度的O(n)算法,这个算法有一个名字Manacher。
具体原理与实现:
假设存在一字符串 waabwswfd
我们将在该字符串各字符之间以及边缘各插入一个特殊字符#构造新的字符串 #w#a#a#b#w#s#w#f#d ,这样做的好处是可以不用区分奇数串还是偶数串。
并定义变量P[i]为新字符串中以第i个字符为中心的回文串其中心至边缘的距离,那么P[i]-1就是原串中回文的长度
此外,再定义两个状态变量id和mx,即当遍历到某位置i时,mx记录以i之前的位置为中心形成的回文串的最右边界的下标,id为这个回文串的中心下标,
我们通过遍历一次数组,
当mx>i时,存在两种情况
1.mx-i<=i-id,此时可以确定的以i为中心的回文串长度为P[2*id-i](根据性质回文串左右两边是相同的,因此以其中字符为中心的回文串长度也相同
2.mx-i>i-id,此时以i为中心的回文串可能通过使用mx之后的字符形成更长的字符串,而其对于id对称的字符所形成的回文使用了范围之外的字符所以无法用P[2*id-i]进行参考,(可以确定的P[i]只能在mx的限定范围内,因此此时令P[i]=mx-i
这样就得到了初始的P[i],现在继续判断边界是否可以扩充,由于每次扩充必然会造成对于第i+1次循环时mx值的递增,因此整个过程对于mx的值而言是线性递增的。
附其他博文中的一张图以便于理解
#include<iostream> #include<cstring> #define Min(a,b) (a<b?a:b) #define Max(a,b) (a<b?b:a) using namespace std; int main(){ char s1[300000]; char s2[300000]; int P[300000]; while(~scanf("%s",s1)){ memset(P,0,sizeof(P)); s2[0]='$'; s2[1]='#'; int l=strlen(s1); for(int i=0;i<l;++i){ s2[2*i+1+1]=s1[i]; s2[2*i+2+1]='#'; } l=l*2+1+1; s2[l]='\0'; int mx=0,id=0; for(int i=0;i<l;++i){ if(mx>i) P[i]=Min(mx-i,P[2*id-i]); else P[i]=1; for(;s2[i-P[i]]==s2[i+P[i]];P[i]++); if(i+P[i]>mx){ mx=i+P[i]; id=i; } } int ans=1; for(int i=0;i<l;++i) ans=Max(P[i]-1,ans); printf("%d\n",ans); } return 0; }
注意不要在循环里面用strlen。。
time limited了一万年Orz....