好文转载
luoguP3804
代码：
/* 定义.对给定字符串s的后缀自动机是一个最小化确定有限状态自动机，它能够接收字符串s的所有后缀。 对给定字符串s的后缀自动机是一个最小化确定有限状态自动机，它能够接收字符串s的所有后缀。 某一状态t_0被称作初始状态，由它能够到达其余所有状态。 自动机中的所有转移——即有向边——都被某种符号标记。从某一状态出发的诸转移必须拥有不同的标记。（另一方面，状态转移不能在任何字符上）。 一个或多个状态被标记为终止状态。如果我们从初始状态t_0经由任意路径走到某一终止状态，并顺序写出所有经过边的标记，你得到的字符串必然是s的某一后缀。 在符合上述诸条件的所有自动机中，后缀自动机有这最少的顶点数。（后缀自动机并不被要求拥有最少的边数） 最简性：它包含了所有s的子串的信息。换言之，对于任意从初始状态t_0出发的路径，如果我们写出所经过边上的标记，形成的子串必须是s的子串。相应地，s的任意子串都对应一条从初始状态t_0出发的路径。 为了简化说明，我们称子串“匹配”了从初始状态出发的路径，如果该路径上的边标记组成了这一子串。相应地，我们称任意路径“匹配”某一子串，该子串由路径中边的标记组成。 后缀自动机的每个状态都引领一条或多条从初始状态出发的路径。我们称这个状态有若干匹配这些路径的方法。 引理1.两个非空子串u和v（length(u)<=length(v)）是终点等价的，当且仅当u在字符串s中仅作为w的后缀出现。 引理2.考虑两个非空子集u,w（length(u)<=length(w)）。它们的终点集合不相交，或者endpos(w)是endpos(u)的子集。进一步地，这取决于u是否是w的后缀： 引理3.考虑一个终点等价类。将该等价类中的子串按长度递减排序。排序后的序列中，每个子串将比上一个子串短，从而是上一个字串的后缀。换句话说，某一终点等价类中的字符串互为后缀，它们的长度依次取区间[x,y]内的所有数。 引理4.后缀链接组成了一棵以t_0为根的树。 引理5.如果我们将所有合法的终点集合建成一棵树（使得孩子是父母的子集），这棵树将和后缀链接构成的树相同。 状态的数量： 由长度为n的字符串s建立的后缀自动机的状态个数不超过2n-1（对于n>=3）。 转移的数量： 由长度为n的字符串s建立的后缀自动机中，转移的数量不超过3n-4（对于n>=3）。 定理1.DAWG(s)中后缀链接组成的树就是后缀树ST(rev(s))。 定理2.图DAWG(s)的边都能用后缀树ST(rev(s))的扩展指针表示。另外，DAWG(s)中的连续转移就是ST(rev(s))中反向的后缀指针。 定理3.使用后缀自动机DAWG(s)，我们可以用O(n)的时间构建后缀树ST(rev(s))。 定理4.使用后缀树ST(rev(s))，我们可以用O(n)的时间构建后缀自动机DAWG(s)。 */ #include <cstdio> #include <complex> #include <cstring> #ifdef Win32 #define LL "%I64d" #else #define LL "%lld" #endif const int N=2e6+5; typedef long long ll; char s[N]; int a[N],c[N],size[N],n; ll ans=0; inline int max(int x,int y) {return x>y?x:y;} struct SuffixAutoMaton { int last,cnt,ch[N<<1][26],fa[N<<1],l[N<<1]; void ins(int c) { int p=last,np=++cnt; last=np;l[np]=l[p]+1; for(;p&&!ch[p][c];p=fa[p]) ch[p][c]=np; if(!p)fa[np]=1; else { int q=ch[p][c]; if(l[p]+1==l[q]) fa[np]=q; else { int nq=++cnt; l[nq]=l[p]+1; memcpy(ch[nq],ch[q],sizeof(ch[q])); fa[nq]=fa[q]; fa[q]=fa[np]=nq; for(;ch[p][c]==q;p=fa[p]) ch[p][c]=nq; } } size[np]=1; } void build() { scanf("%s",s+1); int len=strlen(s+1); last=cnt=1; for(int i=1;i<=len;++i) ins(s[i]-'a'); } void calc() { for(int i=1;i<=cnt;++i)++c[l[i]]; for(int i=1;i<=cnt;++i)c[i]+=c[i-1]; for(int i=1;i<=cnt;++i)a[c[l[i]]--]=i; for(int i=cnt;i;--i) { int p=a[i]; size[fa[p]]+=size[p]; if(size[p]>1) ans=max(ans,1LL*size[p]*l[p]); } printf(LL " ",ans); } }sam; int main() { sam.build(); sam.calc(); return 0; }