|
试题描述
|
|
输入一个字符串S，输出S的最长连续回文子串长度。 |
|
输入
|
|
输入一个字符串S。
|
|
输出
|
|
输出S的最长连续回文子串长度
|
|
输入示例
|
|
abacbbc
|
|
输出示例
|
|
4
|
|
其他说明
|
|
1<=|S|<=1000000
|
这就是传说中的萌萌哒马拉车算法（manacher）啦
首先为了方便处奇偶两种情况，将S重新变成新的字符串T，如abacddc变成#a#b#a#c#d#d#c#
再次为了方便处理越界，将字符串首尾加一个奇怪的不匹配字符，如将abacddc变成~#a#b#a#c#d#d#c#`
请大家想一想这样的好处
考虑暴力算法，枚举回文串中心，暴力向两边匹配
rep(1,n-1) { int t=1; while(s[i-t]==s[i+t]) t++; ans=max(ans,t-1); }
这样是O(N^2)，考虑优化
我们定义P[i]表示位置i的最长匹配长度，考虑利用之前的匹配信息。
这样就是p[i]=p[2*id-i]
这样就是p[i]=mx-i
写成代码就是这样
#include<cstdio> #include<cctype> #include<queue> #include<cstring> #include<algorithm> #define rep(s,t) for(int i=s;i<=t;i++) #define ren for(int i=first[x];i!=-1;i=next[i]) using namespace std; inline int read() { int x=0,f=1;char c=getchar(); for(;!isdigit(c);c=getchar()) if(c=='-') f=-1; for(;isdigit(c);c=getchar()) x=x*10+c-'0'; return x*f; } const int maxn=2000010; char s[maxn]; int p[maxn]; int solve(char* s2) { int n=1,id=0,mx=0,ans=0; for(int i=0;s2[i]!=' ';i++) s[n++]='#',s[n++]=s2[i]; s[0]='~';s[n++]='#';s[n++]='`'; rep(1,n-1) { if(mx>i) p[i]=min(p[2*id-i],mx-i); else p[i]=1; while(s[i+p[i]]==s[i-p[i]]) p[i]++; if(i+p[i]>mx) mx=i+p[i],id=i; ans=max(ans,p[i]-1); } return ans; } char s2[maxn]; int main() { scanf("%s",s2); printf("%d ",solve(s2)); return 0; }
为什么是O(N)的呢？
因为算法只有遇到还没有匹配的位置时才进行匹配，已经匹配过的位置不再进行匹配，所以对于T字符串中的每一个位置，只进行一次匹配，所以Manacher算法的总体时间复杂度为O(n)，其中n为T字符串的长度，由于T的长度事实上是S的两倍，所以时间复杂度依然是线性的。
补一个PAM的（以后不能装*，将”f[np]=to[k][c];to[p][c]=np;“i写成”f[to[p][c]=np]=to[k][c];“就会T飞，因为k可能等于p）
#include<cstdio> #include<cctype> #include<queue> #include<cstring> #include<algorithm> #define rep(s,t) for(int i=s;i<=t;i++) #define ren for(int i=first[x];i!=-1;i=next[i]) using namespace std; inline int read() { int x=0,f=1;char c=getchar(); for(;!isdigit(c);c=getchar()) if(c=='-') f=-1; for(;isdigit(c);c=getchar()) x=x*10+c-'0'; return x*f; } const int maxn=1000010; char ch[maxn]; struct PAM { int cnt,last; int to[maxn][26],f[maxn],l[maxn]; PAM() {cnt=f[0]=1;l[1]=-1;} void extend(int c,int n) { int p=last; while(ch[n]!=ch[n-l[p]-1]) p=f[p]; if(!to[p][c]) { int np=++cnt,k=f[p];l[np]=l[p]+2; while(ch[n]!=ch[n-l[k]-1]) k=f[k]; f[np]=to[k][c];to[p][c]=np; } last=to[p][c]; } int solve() { int ans=0; rep(1,cnt) ans=max(ans,l[i]); return ans; } }sol; int main() { scanf("%s",ch+1);int n=strlen(ch+1); rep(1,n) sol.extend(ch[i]-'a',i); printf("%d ",sol.solve()); return 0; }