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

~~太菜了现在才会SAM~~ 网上的教程实在太玄学了…… 但是如果想要了解后缀自动机一些比较棒的性质还是有必要了解的 但是这些几乎对大家码代码几乎没啥用…… 所以这里写一篇后缀自动机(suffix automation，SAM)的教程好了 ## 前置芝士：确定性有限状态自动机(DFA) 一个确定性有限状态自动机是一堆“零件”的集合，可以“识别”一些字符串 _标准的定义是一个由(Q, Σ, δ, q0, F)构成的5元组，但是这里并不讲解正规定义_ 如果实用一点来讲的话，DFA是一张图，有一个开始节点，代表空串，有一堆点，各个点并没有实际意义(准确来讲部分自动机，但是不是所有的自动机都要求节点有意义)，点之间有边。 和普通的图区别最大的一点就是，DFA的图的边是有实际意义的，一条边代表了**一种字符**，一个点必须有且仅有每一个字符的出边(如果某个出边无意义，一般的做法是这个出边指向NULL节点) 那么我们发现，如果从起点出发，走出一条路径(随便走，并不要求简单路径)，那么这个路径可以代表一个字符串。 定义一个字符串可以被一个DFA“识别”就是我们从初始点出发，走出这个字符串(显然这个路径必须是存在且唯一的，因为每个节点的某种类型的出边有且仅有一条)之后，我们到达了某些我们指定的节点上，那么就认为这个节点可以被这个自动机识别，另外这些节点在某些博客中被称为“接受节点” ## 前置芝士：子串表示法 我们发现一件事是，我们的后缀自动机，顾名思义，就是可以识别某个字符串S所有的后缀的自动机，会有这样的的性质 我们对这个自动机输入一个任意字符串a,如果这个字符串还在自动机的节点上而没有被打回到NULL节点上，那么我们输入的字符串一定是源串的子串(因为此时们还有输入一些字符让它变成一个后缀的可能，不是子串的话就连可能都没有了) 那么我们可以自豪的说，如果我们可以表示一个串所有的子串，我们就可以建出来一个后缀自动机了 一个显而易见的做法是枚举每个子串，然后每个点代表一个子串，子串之间连边，这样的时空复杂度均是$O(N^2)$不可承受 所以让我们想一个机智的办法 我们用一个点的集合right和一个长度len来描述一个子串 这个子串的特点是，这个长度为len的子串在匹配主串S的时候，如果**右端点**∈right，就可以成功匹配，否则不可以成功匹配，显然这样描述了多个位置不同但是写起来一膜一样的子串 当然为了节约资源，如果一堆子串的right集合相同，我们就就将这些子串压到同一个节点上表示，这个节点只记录一个len，代表这个节点表示的所有子串中，len的最大值，但是，我们在具体实现的时候只记录len但是不记录right，原因后面再讲 # 后缀自动机的构建算法 哎哎哎你什么都没讲就开始讲构造？ 这是因为后缀自动机的构造算法是一个名为增量算法的东西，说白了就是一个一个插入字符，这样的话我们就只需要考虑两件事 1.新建几个节点 2.新建的节点连到什么节点上 先来考虑新建几个节点 更加准确的说，加入的这第i个字符会产生几种新子串 第一种是S的第i个前缀，right集合只有i 第二种是S的第i个前缀的某些后缀，right集合有一堆，不只有1 所以好了我们新建两个节点np，nq分别代表第一种和第二种子串 问题来了，谁会向它连边，它又会向谁连边呢？ 尽管后缀自动机节点的意义很复杂，但是，如果把表示的子串写出来，会发现不过是某一个字符串的一些后缀而已，因此边的转移的意义就是在这个字符串上加了一个字符x之后变成了一个新的字符串而已，而这些后缀的长度都增加了1，而个数不变，仅此而已。 所以我们找到表示原来第i-1个前缀的节点，让它连一条标号为x的边到np 但是我们会发现一个非常辣手的问题，别的点的right集合如果包含i-1，那么也存在着转移的可能 所以必须找到每一个right集合包含i-1的节点，要怎么找呢 ## Parent树 我们发现如果将某个节点的表示的串写出来，是某一个字符串的一些后缀 如果我们在字符串前加入一个字符，那么right集合可能会缩小，因为这个串在原串可以匹配的位置可能减少 另外尽管我们只保存了len最大值，但是len最小值也是客观存在的 考虑这个串一个小一点的后缀，比如长度是len的最小值-1，那么这个后缀代表的节点的right集合必然包含原来节点的right集合，因为可以匹配的位置必然增多，否则这个后缀也可以压缩到这个节点里 然后这个right集合的包含关系可以映射为树上的父子关系 所以在后缀自动机中我们令fa\[x]表示可以包含节点x的right集合，且集合元素最小的点(哦对了，显然right集合不是包含就是不交，因为如果有交的话两个节点表示的子串写出来一样，其实就是一个节点) 根据这个父子关系可以构成一个树称为parent树 有了parent树，就不需要存储right集合了，因为现在我们可以找到这个点子树中所有的叶子结点(显然表示的前缀节点是且仅是叶子结点)，就可以找到这个点的right集合了 ------------- 有了parent树，刚才的问题好解决多了，我们枚举第i-1个前缀到树根的所有节点即可 如果这个路径上的节点没有可以转移到x的出边，意味着原来不存在这样的子串，但现在有了，叫np，所以直接连一条标号为x，到np的出边即可 如果我们就这样跑完了整个路径，令fa\[p]=start(开始节点)return即可，**这种情况nq不存在** 另一种比较辣手的情况，路径上节点出现了可以转移到x的出边，并且指向q 此时我们会发现如果两个集合的right集合全等(也就是maxlen(当前节点)+1=maxlen(q)，因为如果最长的串right集合都可以转移，那么其他小一点串当然也可以转移)，我们只需要在q的right集合，以及q的祖先的right集合中插入i即可，所以我们只需要让fa\[np]=q，就完成了隐性插入的工作(抱歉这种情况nq也不存在) 另一种更加辣手的情况，两个集合的right集合不全等 此时证明q已经过时了，该转移到的应该是nq，因为加了一个字符之后写出来的应该是nq代表的字符串，而right集合比q的多，同时，q转移到的点nq都可以，因为这两个串写出来一膜一样，所以复制一边q的出边到nq上，另外当前节点最长的点都可以转移到nq上，所以nq的len应该等于len\[当前节点]+1 此时还没有完，当前结点的祖先如果有连向q的出边，那么都会因为同样的理由过时了，所以全部修改为nq， 最后是parent树的问题，显然nq的right集合是q的right集合∪i(np的right集合)所以令q和np的parent都为nq，同时q的所有祖先还是可以转移的，只是需要加入一个i，同理使用这样的隐性插入法，只需令fa\[nq]=fa\[q]即可 在经历了上述乱七八糟的算法之后，我们终于完成了插入一个字符 但是clj大佬证明了上述的复杂度是均摊$O(1)$换句话来讲，整个sam的构建过程是$O(n)$的 在理解上述算法的时候注意两点 1.建什么新点，连什么新边，parent的树边怎么修改 2.一个节点可能意义比较繁杂，但是写出来的串只有一个串和它的一堆后缀 了解了这两点之后，反复阅读各路神犇的博客，就应该可以掌握SAM的构建了 # 本题题解 额……，我们令叶子节点的size=1.暴力建出parent树然后dfs，求出每个节点的right集合size，然后求$len×size$的最大值就行了 下面就是代码了……(真的很短) 上代码~ ```C #include<cstdio> #include<algorithm> using namespace std;const int N=3*1e6+10;typedef long long ll; char mde[N];int nl;ll res; struct suffixautomation { int mp[N][30];int fa[N];int ed;int ct;int len[N];int siz[N]; suffixautomation(){ed=ct=1;} int v[N];int x[N];int al[N];int cnt; inline void add(int u,int V){v[++cnt]=V;x[cnt]=al[u];al[u]=cnt;} inline void ins(int c) { int p=ed;siz[ed=++ct]=1;len[ed]=nl;//先初始化size和len for(;p&&mp[p][c]==0;p=fa[p]){mp[p][c]=ed;}//然后顺着parent树的路径向上找 if(p==0){fa[ed]=1;return;}int q=mp[p][c];//case1 if(len[p]+1==len[q]){fa[ed]=q;return;}//case2 len[++ct]=len[p]+1;//case 3 for(int i=1;i<=26;i++){mp[ct][i]=mp[q][i];} fa[ct]=fa[q];fa[q]=ct;fa[ed]=ct; for(int i=p;mp[i][c]==q;i=fa[i]){mp[i][c]=ct;} } inline void bt(){for(int i=2;i<=ct;i++){add(fa[i],i);}}//暴力建树 void dfs(int u)//dfs { for(int i=al[u];i;i=x[i]){dfs(v[i]);siz[u]+=siz[v[i]];} if(siz[u]!=1){res=max(res,(ll)siz[u]*len[u]);} } }sam; int main() { scanf("%s",mde+1);//没啥好说的，建sam然后dfs for(nl=1;mde[nl]!='\0';nl++){sam.ins(mde[nl]-'a'+1);} sam.bt();sam.dfs(1);printf("%lld",res);return 0;//拜拜程序~ } ```