后缀自动机模板
ｃｏｄｅ：
#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=3e6+5000; ll res=0; char s[maxn]; int c[maxn],idx[maxn]; /*==================Define Area================*/ namespace SAM { struct node { int len; int son[26]; int fa; }t[maxn]; int sz[maxn]; int tot=1,last=1,rt=1; void insert(int c) { int p=last; int np=++tot; t[np].len=t[p].len+1; sz[np]=1; while(p&&!t[p].son[c]) t[p].son[c]=np,p=t[p].fa; if(!p) t[np].fa=1; else { int q=t[p].son[c],nq; if(t[p].len+1==t[q].len) t[np].fa=q; else { // nq=newnode(t[p].len+1,0); // memcpy(t[nq].son,t[q].son,sizeof t[q].son); nq=++tot; t[nq]=t[q]; t[nq].len=t[p].len+1; t[q].fa=t[np].fa=nq; while(p&&t[p].son[c]==q) t[p].son[c]=nq,p=t[p].fa; } } last=np; } } using namespace SAM; int main() { scanf("%s",s); int n=strlen(s); for(int i=0;i<n;i++) insert(s[i]-'a'); for(int i=1;i<=tot;i++) c[t[i].len]++; for(int i=1;i<=n;i++) c[i]+=c[i-1]; for(int i=1;i<=tot;i++) idx[c[t[i].len]--]=i; for(int i=tot;i;i--) { int p=idx[i]; sz[t[p].fa]+=sz[p]; if (sz[p]>1) res=max(res,1ll*sz[p]*t[p].len); } printf("%lld\n",res); return 0; return 0; }转载于:https://www.cnblogs.com/Apocrypha/p/9430683.html
相关资源：JAVA上百实例源码以及开源项目