因为manacher算法把原来的字符串扩大了两倍，因此在应用时许多二级结论都非常不直观，现场推出来很麻烦，因此笔者在此做个简单整理，如果发现有错误或者有常用的我没有涉及到的，恳请在下方评论区指出，我会非常感谢。
#include<iostream> #include<cstdio> #include<cstring> #define MAXN 200005 using namespace std; char str[MAXN]; char ex[MAXN*2]; int rad[MAXN*2]; void make_char(const char *str,char *ex){ int l=strlen(str); int i,j; j=0; ex[0]='$'; for(i=0;i<l;i++){ ex[++j]='#'; ex[++j]=str[i]; } ex[++j]='#'; ex[++j]=' '; } int manacher(const char *ex,int *rad){ int l1=strlen(ex); int mx=0,id=0,i=0; int maxx=0; rad[0]=0; for(i=1;i<l1;i++){ if(i>=mx)rad[i]=1; else rad[i]=min(mx-i+1,rad[2*id-i]); while(ex[i-rad[i]]==ex[i+rad[i]]){ rad[i]++; } if(i+rad[i]-1>mx){ id=i; mx=i+rad[i]-1; } maxx=max(maxx,rad[i]-1); } return maxx; } int main(){ scanf("%s",str); make_char(str,ex); printf("%d ",manacher(ex,rad)); return 0; }
1，rad数组虽然指的是回文半径，但是它的值减一和回文子串长度对应
因此，最长回文子串长度是
max(ans[i]-1)
2，怎么对应呢，引入一个“某位置在ex上对应位置”概念
str[i]对应于ex[2i+2]
str[l,r]对应于ex[2*l+2,2*r+2]
ex[l+r+2]是该子串在ex上的中点
要问str上的子串[l,r]是不是回文子串
只需判断rad[l+r+2]-1>=r-l+1即可
3，假设t是str上某个点，t为整数时此点为某个字符，t不是整数时夹在两个字符串中间
那么以t为中点的最长回文子串的长度是rad[ans[2t+2]]-1
令tmp=rad[ans[2t+2]]-2
对应到str上的字符串是str[t-(tmp/2),t+(tmp)/2)
4，子串的回文子串
对于子串str[l,r]
将ans[2l+1,2r+3]如此构造：
ans'[i]=min(ans[i],l-i+1,r-i+1)
配合数据结构食用更佳