[模版]后缀自动机-学习笔记

神仙般的算法，表示看了一晚上+一上午才勉强过了模板题，不过还好，没怎么抄题解。 虽然clj的课件有很多锅，但是还是说了很多性质的，勉强能够看下来，这里有一些很好的博客： [图解，好评！对新建节点尤其有帮助](https://www.cnblogs.com/GBRgbr/p/3236451.html) [证明len的关系](http://blog.sina.com.cn/s/blog_70811e1a01014dkz.html) 说说自己的理解（借鉴前人的说法） ### 有限状态自动机 简单说就是一个程序，给它一个信息，它会告诉你这个信息是不是存在。对于SAM来说，就是可以接受一个串的所有后缀的自动机。 实现SAM最暴力的方法就是把所有后缀插入到Trie树上，$O(N^2)$，所以我们需要**最简状态后缀自动机**。 ### 子串表示法 如何表示一个子串？我们定义一个字符串t在母串s中的right集合表示：所有t在s中的出现位置的结尾的下一个位置（我习惯下标从1开始），例如aabaab中，ab的right集合为$\{4,7\}$。同时，会有多个字符串的right集合是相同的，比如aab的right也是4,7，而一个right集合对应的子串的长度是一个范围，记为$[\min(),\max()]$。 为什么是有上下界的？因为如果过短，可能这个短串在更多的地方出现了；如果过长，可能某个位置没有这个串了。 一个**状态**s，有所有right集合为right(s)的字符串组成。 ### 任意两个串的right集合，要么不相交，要么一个是另一个的真子集 这也能够证明状态数是线性的。  然而不一定每个right集合都对应一个串。 **right集合实际上构成了一个树形结构，不妨称其为Parent树，树的大小为$O(N)$**  $Max(fa)=Min(s)-1$ ### 证明边的大小是$O(N)$的  ### 关于子串的性质 每个子串都包含在SAM的某个状态里，子串的出现次数即为所在状态的right集合的大小。 ## 构造SAM：增量法 直接说明方法： 首先，SAM里的end状态即为：最末端的状态的parent祖先。 考虑$SAM(T)\to SAM(Tx)$，添加一个字符x，我们一定是在所有后缀的结尾处添加一个x，既然是后缀的结尾，就一定是end状态。首先，最末端的点（即为last）要接上x，所以新建一个节点np表示字符x，$ch[last][x]=np$。 然后考虑last的祖先，一点点往上跳，如果祖先p没有x这个儿子，就令$ch[p][x]=np$。 当发现第一个祖先p有x这个儿子，我们怎么办？ 我们再多维护一个len[i]表示原点到i的最长路。 令$q=ch[p][x]$，如果len[q]=len[p]+1，说明从p到q只有这一条路，那么我们不用新建节点了，直接令fa[x]=q即可。 否则，我们不能直接令fa[x]=q，否则可能会把一些不是后缀的串认为是后缀，具体的看一下开头的有图解的博客。 于是我们新建一个节点nq，令$fa[nq]=fa[q],fa[np]=fa[q]=nq,ch[p][x]=nq$，这样就OK了。 ```cpp int ins(int x,int w) { int np=++tot; len[np]=len[x]+1; while(x&&!ch[x][w]) ch[x][w]=np,x=fa[x]; if(!x) fa[np]=rt; else { if(len[ch[x][w]]==len[x]+1) fa[np]=ch[x][w]; else { int q=ch[x][w],nq=++tot; len[nq]=len[x]+1,fa[nq]=fa[q]; for(ri i=0; i<26; ++i) ch[nq][i]=ch[q][i]; fa[np]=fa[q]=nq; while(x&&ch[x][w]==q) ch[x][w]=nq,x=fa[x]; } } return np; } ``` ## SAM与DAWG SAM的边不是一棵树，是一个DAG，这就给了它很好的性质。 如何求出SAM中每个点的拓扑序？有点类似SA的基数排序的方法： ```cpp for(ri i=1; i<=tot; ++i) ++buk[len[i]]; for(ri i=1; i<=n; ++i) buk[i]+=buk[i-1]; for(ri i=1; i<=tot; ++i) pos[buk[len[i]]--]=i; ``` 注意到len就唯一对应一个拓扑序。 ## 广义后缀自动机 就是多串的SAM，包含多串的不重复子串。 构造方法就是一个个的插入字符串，每插入一个字符串就把当前的last设为rt，继续插入。 ## 后缀自动机转后缀树 后缀树的定义其实是和后缀自动机的parent树是反的，parent树的fa是当前串的后缀，而后缀树的fa是当前串的前缀，所以我们从后往前插入字符，得到SAM，然后我们在建SAM时记录一下每个点在原串的位置，再记录一下**每条边压缩的长度即可**，压缩的长度即为len[fa]。 [这个人的博客很棒](https://blog.csdn.net/lvzelong2014/article/details/79006541) ## 后缀树转后缀数组 就是DFS一遍后缀树，依次记录就是SA。 复杂度$O(N\times \text{字符集大小})$ 但是为了求SA而跑SAM建ST真是一个愚蠢的事情，很慢的。 ## SAM的拓扑序和Parent树的父子序近似相同 ## 广义的SAM不能用len求拓扑序！