题解 P3804 【【模板】后缀自动机】

[SAM](https://www.cnblogs.com/xzyxzy/p/9186759.html)<身为机房最后一个学SAM的最弱的人折腾了近一周写了一个较为详细的总结> 先把串建好后缀自动机，再拓扑parent树，统计答案 代码中有详细注释，专门给大概了解如何构建SAM但是代码实现有难度的同学食用 ```cpp #include<iostream> #include<cstdio> #include<cstdlib> #include<cstring> #define ll long long using namespace std; const int N=2010000; char s[N]; int fa[N],ch[N][26],len[N],siz[N]; int lst=1,node=1,l,t[N],A[N]; ll ans; void Extend(int c) { /* 2+2+2+3行，那么多while但是复杂度是O(n) */ int f=lst,p=++node;lst=p; len[p]=len[f]+1;siz[p]=1; /* f为以c结尾的前缀的倒数第二个节点，p为倒数第一个（新建） len[i] 表示i节点的longest，不用记录shortest（概念在hihocoder后缀自动机1上讲得十分详细） siz[i]表示以i所代表的endpos的集合元素大小，即所对应的字符串集出现的次数 不用担心复制后的siz，在parent树上复制后的点的siz是它所有儿子siz之和，比1多 */ while(f&&!ch[f][c]) ch[f][c]=p,f=fa[f]; if(!f) {fa[p]=1;return;} /* 把前面的一段没有c儿子的节点的c儿子指向p Situation 1 如果跳到最前面的根的时候，那么把p的parent树上的父亲置为1 */ int x=ch[f][c],y=++node; if(len[f]+1==len[x]) {fa[p]=x;node--;return;} /* x表示从p一直跳parent树得到的第一个有c儿子的节点的c儿子 Situation 2 如果节点x表示的endpos所对应的字符串集合只有一个字符串，那么把p的parent树父亲设置为x Situation 2 和 Situation 3 本质不同！！！与机房dalao们讨论两天才知道Situation 2 必须特判的原因！！！详见上方链接的博客 */ 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]; /* Situation 3 否则把x点复制一遍（parent树父亲、儿子），同时len要更新 （注意len[x]!=len[f]+1,因为通过加点会使x父亲改变） 然后把x点和p点的父亲指向复制点y，再将前面所有本连x的点连向y */ } int main() { //Part 1 建立后缀自动机 scanf("%s",s); l=strlen(s); for(int i=l;i>=1;i--) s[i]=s[i-1];s[0]=0; for(int i=1;i<=l;i++) Extend(s[i]-'a'); //Part 2 按len从大到小排序（和SA好像啊）后计算答案 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--) {//从小到大枚举，实际上在模拟parent树的DFS 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; } ```