回文自动机模板
ｃｏｄｅ：
#include <bits/stdc++.h> using namespace std; typedef long long ll; bool Finish_read; template<class T>inline void read(T &x){Finish_read=0;x=0;int f=1;char ch=getchar();while(!isdigit(ch)){if(ch=='-')f=-1;if(ch==EOF)return;ch=getchar();}while(isdigit(ch))x=x*10+ch-'0',ch=getchar();x*=f;Finish_read=1;} template<class T>inline void print(T x){if(x/10!=0)print(x/10);putchar(x+'0');} template<class T>inline void writeln(T x){if(x<0)putchar('-');x=abs(x);print(x);putchar('\n');} template<class T>inline void write(T x){if(x<0)putchar('-');x=abs(x);print(x);} /*================Header Template==============*/ const int maxn=1e5+50; char s[maxn]; int ret[maxn]; /*==================Define Area================*/ struct pldTree { struct node { int son[30]; int fail,len; }t[maxn]; int last,tot; void init() { t[0].fail=t[1].fail=1; t[tot=1].len=-1; } void insert(int c,int n,char *s) { int p=last; while(s[n-t[p].len-1]!=s[n]) p=t[p].fail; if(!t[p].son[c]) { int o=++tot,k=t[p].fail; t[o].len=t[p].len+2; while(s[n-t[k].len-1]!=s[n]) k=t[k].fail; t[o].fail=t[k].son[c]; t[p].son[c]=o; } last=t[p].son[c]; } }T1,T2; int main() { scanf("%s",s+1); int n=strlen(s+1); T1.init();T2.init(); for(int i=1;i<=n;i++) { T1.insert(s[i]-'a',i,s); ret[i]=T1.t[T1.last].len; } reverse(s+1,s+n+1); for(int i=1;i<=n;i++) { T2.insert(s[i]-'a',i,s); ret[n-i]+=T2.t[T2.last].len; } int res=0; for(int i=1;i<=n;i++) { res=max(res,ret[i]); } printf("%d\n",res); return 0; }转载于:https://www.cnblogs.com/Apocrypha/p/9430671.html
相关资源：JAVA上百实例源码以及开源项目