后缀自动机的模板

后缀自动机真是个好东西

#include 
#define cl(a) memset(a,0,sizeof(a))
#define ll long long
#define pb(i) push_back(i)
#define sc(x) scanf("%d",&x)
using namespace std;
const int maxn=2010000;
const int inf=0x3f3f3f3f;
const int mod=1e9+7;
typedef pair PII;
ll fpow(ll n, ll k) {ll r = 1; for (; k; k >>= 1) {if (k & 1) r = r * n; n = n * n;} return r;}
char s[maxn];
int fa[maxn],ch[maxn][26],len[maxn],siz[maxn];
int lst=1,node=1,l,t[maxn],A[maxn];
ll ans;
void extend(int c)
{int f=lst,p=++node;lst=p;len[p]=len[f]+1;siz[p]=1;while(f&&!ch[f][c]) ch[f][c]=p,f=fa[f];if(!f){fa[p]=1;return;}int x= ch[f][c],y=++node;if(len[f]+1==len[x]){fa[p]=x;node--;return;}len[y]=len[f]+1;fa[y]=fa[x];fa[x]=fa[p]=y;memcpy(ch[y],ch[x],sizeof(ch[y]));while(f&&ch[f][c]==x) ch[f][c]=y,f=fa[f];
}
int main()
{scanf("%s",&s[1]);l= strlen(&s[1]);for(int i=1;i<=l;i++) extend(s[i]-'a');for(int i=1;i<=node;i++) t[len[i]]++;for(int i=1;i<=node;i++) t[i]+=t[i-1];for(int i=1;i<=node;i++) A[t[len[i]]--]=i;for(int i=node;i>=1;i--){int now = A[i];siz[fa[now]]+=siz[now];if(siz[now]>1) ans=max(ans,1ll*siz[now]*len[now]);}printf("%lld\n",ans);return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！