俗称马拉车算法->_->
处理最长回文字串复杂度O(n)
这里菜鸡不会证,简单说一下思路。
由于回文串有奇有偶,所以将串之间和两边加上'#',为了防止后面某个地方超边界,新串0位置加上$。这样每个回文子串为#a#b#a#形式,必定奇数个,且原子串长度为新字串半径减一,求这个半径p[i]。(即p[i]是以i为中心的最长回文字串的半径)
i从1到n,过程中维护一个id点(id<i,i拉着id走,马拉车),它是某个回文子串的中心,这个字串右边界是当前最大的。(p[i]是半径,故i+p[i]为边界)
那么当右边界比i还大时,就可以根据对称性,找到i关于id的对称点j=2*id-i,来优化找字串的过程。怎么优化呢?在id管辖范围内,p[i]和p[j]情况是相同的。由于超出id右边界的的地方不符合对称性,因此p[i]=p[j]当且仅当p[j]小于等于j-(id-p[id])(即j串的左边界不超出id串的左边界),否则只能直接到id右边界,p[i]=mx-i,之后的手动算。
如果id右边界太小,不能做优化,也得手动算。
以下代码:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43
| #include<iostream> #include<cstdio> #include<cstring> #include<string> #define ll long long using namespace std; char s[100020],sn[200020]; int p[200020]; int init(){ int len=strlen(s); sn[0]='$';sn[1]='#'; int j=2; for(int i=0;i<len;i++){ sn[j++]=s[i]; sn[j++]='#'; } sn[j]='\0'; return j; } int Manacher(){ int len=init(); int mx_len=-1,id,mx=0; for(int i=1;i<len;i++){ if(i<mx){ p[i]=min(p[2*id-i],mx-i); } else{ p[i]=1; } while(sn[i-p[i]]==sn[i+p[i]]) p[i]++; if(p[i]+i>mx){ id=i; mx=p[i]+i; } mx_len=max(mx_len,p[i]-1); } return mx_len; } int main(){ cin>>s; cout<<Manacher(); return 0; }
|