大体思路

为方便，考虑一个字符串与其奇数长回文子串（以$1$为起点，$n$为终点）。 设$i$为当前位置，$p$为当前触及最右回文子串的中心，$j$为$i$关于$p$的对称位置，$r$为触及最右回文子串的最右端，$l$为触及最右回文子串的最左端，$d1[j]$为$j$的回文半径（如果以$j$为中心的回文串长度为$3$，回文半径为$\frac{3+1}{2}=2$）。 首先有关系$l+r=i+j$，$l+r=2\times p$。 利用回文串的特性，我们考虑两种情况：

$i<r$： （1）$i+d1[j]-1>r$，即$i$若加上$j$的回文半径，位置超过了此时的$r$。那么至少有$d1[i]=r-i+1$，如果$j$的回文串最左边达到了位置$1$，此时$d1$还有更长的可能；否则，$d1$已确定。为了简化分类讨论，直接进行朴素发扩展。 （2）$i+d1[j]-1<=r$，即$i$加上$j$的回文半径还是没有超过$r$。此时$d1[i]=d1[j]$已经确定。$i>=r$： 朴素法扩展。

可以看到，为了简化分类讨论，我们将两种情况合并。 即先判断是否有$i<=r$，如果有，$d1[i]=min(r-i+1,d1[j])$，否则$d1[i]=1$。 然后从该位置进行暴力扩张。

关键代码： 注：此处的$r$代表的是我们上述说的$r+1$，但是$d1$的含义完全一致。

void manacher_odd(char str[]){ for(int i=1,l=1,r=0;i<=n;++i){ int k = (i>r)?1:min(d1[l+r-i],r-i); while(1<=i-k&&i+k<=n&&str[i-k]==str[i+k]) k++; d1[i] = k--; if(i+k>r) l=i-k,r=i+k; // 记得更新触及最右回文子串 } }

偶数长度

与奇数长度的处理是一致的。 不过要考虑边界、长度等细节问题。 此时，$i+j=l+r+1$。以$i$作为当前回文串的右中心。

void manacher_even(char str[]){ for(int i=1,l=1,r=0;i<=n;++i){ int k = (i>r)?0:min(d2[l+r-i+1],r-i+1); while(1<=i-k-1&&i+k<=n&&str[i-k-1]==str[i+k]) k++; d2[i] = k--; if(i+k>r) l=i-k-1,r=i+k; } }

合并偶数与奇数：

把原字符串进行插入字符的处理，将所有回文子串都变成奇数串，进行统一处理。 板子： 字符串为$#a#b#a#a#的形式 新串与原串位置对应关系： 新串的第i个字符，与原串的对应：就是原串第i/2个字符。 新串得到的数组di[i]，在新串中意思是包括中心字符在内的回文半径长度。在原串中，di[i]-1为以第i/2个字符为中心的回文串长度。

string Manacher(string s){ string t="$#"; for(int i=0;i<s.size();++i) t+=s[i],t+='#'; vector<int> p(t.size(),0); int mx=0,id=0; for(int i=1;i<t.size();++i){ p[i]=mx>i?min(p[2*id-i],mx-i):1; while(t[i+p[i]]==t[i-p[i]]) ++p[i]; if(mx<i+p[i]) mx=i+p[i],id=i; } return ; }

求最长的靠左或靠右的回文串：

string Manacher(string s){ string t="$#"; for(int i=0;i<s.size();++i) t+=s[i],t+='#'; // 插入字符 vector<int> p(t.size(),0); // 即d1数组，半径数组 int mx=0,id=0,reslen=0,rescenter=0; for(int i=1;i<t.size();++i){ p[i]=mx>i?min(p[2*id-i],mx-i):1; while(t[i+p[i]]==t[i-p[i]]) ++p[i]; if(mx<i+p[i]) mx=i+p[i],id=i; if(reslen<p[i]&&//如果当前回文串长于维护的最长回文串 //且他满足在原串中靠左或靠右的条件 (((i-p[i])/2==0)||(((i-p[i])/2+p[i]-2)==s.size()-1))){ reslen=p[i]; // 更新 rescenter=i; // 更新中心 } } // 返回这个最长的靠左或靠右的回文串 return s.substr((rescenter-reslen)/2,reslen-1); }

模板

力扣5：求最长回文子串

string preProcess(int len,string s){ if(len==0) return "^$"; string ret="^"; for(int i=0;i<len;++i) ret+="#",ret+=s[i]; ret+="#$"; return ret; } string manacher(int len,string s){ string T=preProcess(len,s); int n=T.length(); int C=0,R=0; for(int i=1;i<n-1;i++){ int i_mirror=2*C-i; if(R>i) P[i]=min(R-i,P[i_mirror]);// 防止超出 R else P[i]=0;// 等于 R 的情况 // 碰到之前讲的三种情况时候，需要利用中心扩展法 while(T[i+1+P[i]]==T[i-1-P[i]]) P[i]++; // 判断是否需要更新 R if(i+P[i]>R) C=i,R=i+P[i]; } // 找出 P 的最大值 int maxLen=0,centerIndex=0; for(int i=1;i<n-1;i++) if(ed==len&&P[i]>maxLen) maxLen=P[i],centerIndex=i; //最开始讲的求原字符串下标 int st=(centerIndex-maxLen)/2,ed=st+maxLen; return s.substr(start,start+maxLen); }

2020牛客国庆d1 ABB

#include<bits/stdc++.h> using namespace std; #define fi first #define se second #define U unsigned #define LL long long #define pb push_back #define MP std::make_pair #define V std::vector<int> #define all(x) x.begin(),x.end() #define CLR(i,a) memset(i,a,sizeof(i)) #define FOR(i,a,b) for(int i = a;i <= b;++i) #define ROF(i,a,b) for(int i = a;i >= b;--i) #define DEBUG(x) std::cerr << #x << '=' << x << std::endl #define INF 0x3f3f3f3f const int N=4e5+5; int P[2*N]; string preProcess(int len,string s){ if(len==0) return "^$"; string ret="^"; for(int i=0;i<len;++i) ret+="#",ret+=s[i]; ret+="#$"; return ret; } int manacher(int len,string s){ string T=preProcess(len,s); int n=T.length(); int C=0,R=0; for(int i=1;i<n-1;i++){ int i_mirror=2*C-i; if(R>i) P[i]=min(R-i,P[i_mirror]); else P[i]=0; while(T[i+1+P[i]]==T[i-1-P[i]]) P[i]++; if(i+P[i]>R) C=i,R=i+P[i]; } int maxLen=0; for(int i=1;i<n-1;i++){ int st=(i-P[i])/2,ed=st+P[i]; if(ed==len&&P[i]>maxLen) maxLen=P[i]; } return len-maxLen; } int main(){ int len;scanf("%d",&len); string s; cin>>s; int ans=manacher(len,s); printf("%d\n",ans); }

Reference

OI wiki 知乎：一文搞懂马拉车 B站：湘潭大学manacher讲解