# **Manacher算法** ## **Manacher算法概述** Manacher算法是用来解决字符串问题中经典的最长回文子串问题的。对于长度为n的字符串， 计算出该字符串的最长回文子串的长度，我们可以直接想到的有两种算法。 （1）枚举左端点和右端点L和R，每次判断[L,R]是否为回文，这样的复杂度为O(n^3) （2）枚举对称轴mid，向左右扩展，更新最大值，复杂度为O(n^2) 而Manacher算法可以在线性时间内来解决这个问题。 ## **Manacher算法过程** ### **step1.预处理** 由于对于给定的字符串的长度奇偶不确定，因此我们对一个给定的字符串，首位以及每两个字符之间插入一个从来没有出现过的字符比如'*'。假设给定的字符串为 ``` aba ``` 那么经过处理之后的字符串就变成了 ``` *a*b*a* ``` ### **step2.辅助数组** 我们定义p[i]为以i为中心，最长的回文半径的长度。对于上面的 ``` *a*b*a* ``` 其对应的p数组为 ``` 1 2 1 4 1 2 1 ``` 不难发现，我们所要求的最长回文字串 的长度即为max(p[i]-1)，那么我们接下来的任务就是在线性的时间内求解出数组p。 ### **step3.辅助数组的求解** 求解p数组的时候我们需要两个变量：pos和maxxright pos代表当前能延伸到最右端的回文字串的中心位置。 maxxright为能延伸到的最右端,显然maxxright=pos+p[pos]-1 上面的两个变量是已知的，那么我们如何求解p[i]呢？ 对于i来说，它一定是大于pos的。那么我们只需要判断i和maxxright的关系即可。 也就是两种情况： 第一种：maxxright>i 这种情况下我们可以找到i关于pos对称的位置j，那么我们可以直接先让p[i]=p[j] (这个不用证明，看图就懂了)  但是如果p[j]太大呢？ 那么p[i]就要对maxxrigth-i取个最小值才可以。  第二种：i<=maxxright 此时直接让p[i]=1,即可。 但是这样还没有算完p[i],我们仍需要进行两边扩展，直到s[i-p[i]]!=s[i+p[i]] 如果计算出来的i+p[i]-1大于当前的maxxright,maxxright和pos就要进行更新了。 这样经过了p数组的优化，每个字符串扩展比较的次数是很少的。最终的复杂度为O(n) ## **code** ``` #include<bits/stdc++.h> using namespace std; const int N = 1e6+100; int p[N]; string s; int manacher(string s){ string t=""; t+='*'; for(int i=0;i<(int)s.size();i++){ t+=s[i]; t+='*'; } int ans=0; int pos=0;int maxxright=0; for(int i=0;i<(int)t.length();i++){ p[i]=maxxright>i?min(p[2*pos-i],maxxright-i):1;//关键 while(i-p[i]>=0&&i+p[i]<(int)t.length()&&t[i-p[i]]==t[i+p[i]]) p[i]++; if(i+p[i]-1>maxxright){ maxxright=i+p[i]-1; pos=i; } ans=max(ans,p[i]); } return ans-1; } int main(){ cin>>s; cout<<manacher(s)<<endl; return 0; } ``` ## **例题** [**吉哥系列故事——完美队形II**](http://acm.hdu.edu.cn/showproblem.php?pid=4513) 这个题是让求满足从左到对称轴单调递增的最长回文字串的长度，其实就是在扩展的过程中加一个限制条件即可。 还有就是这道题的预处理插入的是一个从未出现的数字。 ``` ~~~ #include<bits/stdc++.h> using namespace std; const int N = 3e5+100; vector<int> p,s; int LR[N]; int manacher(vector<int> &s){ p.clear(); memset(LR,0,sizeof(LR)); int maxx=0; int pos=0; int ans=0; int l=(int)s.size(); p.push_back(300); for(int i=0;i<l;i++){ p.push_back(s[i]); p.push_back(300); } int SIZ=(int)p.size(); for(int i=0;i<SIZ;i++){ if(i<maxx) LR[i]=min(LR[2*pos-i],maxx-i); else LR[i]=1; int now; if(p[i]==300) now=p[i-LR[i]]; else now=p[i]; while(i-LR[i]>=0&&i+LR[i]<SIZ&&p[i-LR[i]]==p[i+LR[i]]){ if(p[i-LR[i]]==300||p[i-LR[i]]<=now){ LR[i]++; now=min(now,p[i-LR[i]]); } else break; } if(i+LR[i]-1>maxx){ maxx=i+LR[i]-1; pos=i; } ans=max(ans,LR[i]); } return ans-1; } int main(){ int T,n,x; scanf("%d",&T); while(T--){ s.clear(); scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d",&x),s.push_back(x); printf("%d\n",manacher(s)); } return 0; } ~~~ ```