這麼簡單的算法現在才學......
https://segmentfault.com/a/1190000008484167?utm_source=tag-newest#articleHeader3
https://www.cnblogs.com/grandyang/p/4475985.html
1.在字符之間加入‘#’使得所有回文串的長度變成奇數,方便處理
2.p[i]數組記錄以 i 為回文中心最長回文的半徑,p[i]-1剛好就是這個串的長度
3.mr,id兩個變量,id為能延伸到最右端mr的回文子串的對稱軸,此時左端點為 mr*2-i,(這兩個變量和循環變量 i 無直接關系
4.核心代碼:
if (i < mr)
p[i] = min(p[2 * id - i], mr - i);
else p[i]=1;
引用其他博客的圖片:
如果 mr - i > p[i],那麼以 j 為中心的回文串包含在以 id 為中心的回文串里,又因為 i,j 對稱,這樣p[i]就肯定等於p[j]了
如果 mr-i <= p[i],那麼綠框內至少是一樣的,外面的不知道,所以先設成綠框長度,以後在更新
如果 mr<=i,那麼就沒辦法了,只能從1開始算
最後接一個while暴力處理沒處理好的情況,在更新一下id和mr
#include<iostream> #include<cstdio> #include<algorithm> #include<cstring> using namespace std; const int maxn=11000005; char s[maxn]; char ss[maxn*2]; int p[maxn*2];//以i为中心最长回文半径 int init(){ int len=strlen(s); ss[0]='$';ss[1]='#'; int l=2; for(int i=0;i<len;i++){ ss[l++]=s[i]; ss[l++]='#'; } ss[l]='\0'; return l;//長度 } int manacher() { int len=init(); int maxlen=-1;//最長回文長度 int id,mr=0;//以id為中心最長回文右邊界mr, for(int i=1;i<len;i++){ if(i<mr) p[i]=min(p[2*id-i],mr-i); else p[i]=1; while(ss[i-p[i]] == ss[i+p[i]])//不需邊界判斷 p[i]++; //每走一步i都比較一下,希望mr盡可能遠,更有機會執行i<mr的代碼提高效率 if(mr<i+p[i]) id=i,mr=i+p[i]; maxlen=max(maxlen,p[i]-1); } return maxlen; } int main() { scanf("%s",s); printf("%d",manacher()); }