51Nod1089最长回文子串 V2（Manacher算法）
俗称马拉车算法→_→
处理最长回文字串复杂度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 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<string> 5 #define ll long long 6 using namespace std; 7 char s[100020],sn[200020]; 8 int p[200020]; 9 int init(){ 10 int len=strlen(s); 11 sn[0]='$';sn[1]='#'; 12 int j=2; 13 for(int i=0;i<len;i++){ 14 sn[j++]=s[i]; 15 sn[j++]='#'; 16 } 17 sn[j]='\0'; 18 return j; 19 } 20 int Manacher(){ 21 int len=init(); 22 int mx_len=-1,id,mx=0; 23 for(int i=1;i<len;i++){ 24 if(i<mx){ 25 p[i]=min(p[2*id-i],mx-i); 26 } 27 else{ 28 p[i]=1; 29 } 30 while(sn[i-p[i]]==sn[i+p[i]]) p[i]++; 31 if(p[i]+i>mx){ 32 id=i; 33 mx=p[i]+i; 34 } 35 mx_len=max(mx_len,p[i]-1); 36 } 37 return mx_len; 38 } 39 int main(){ 40 cin>>s; 41 cout<<Manacher(); 42 return 0; 43 }
投递腾讯等公司10个岗位 >
