最近需要参考一下文本检索的思路，所以看了一下后缀自动机并做了实现。
定义：$\text{tail}(w)$表示词$w$中出现不止一次的最长后缀，比如 $\text{tail}(abcbc) = bc, \text{tail}(aaa) = aa, \text{tail}(aab) = \epsilon$。
定义： 当满足如下条件时，$y$被称为$w$中的新左上下文的第一次出现。
- $w = w_1yw_2$
- $y$在$w_1y$中至少出现两次，而且除了最后一次之外，都必须和一个特定的前缀同时出现
比如$w = abcbc$中第二次出现的$bc$就是在新左上下文的第一次出现。
那么：
- $wa$可以代表等价关系$\equiv_{wa}$上的一个等价类，它包含所有出现在$wa$子词集合中而不在$w$字词集合中的元素。
- 对于$w$的一个子词$x$，如果$x$表示等价关系$\equiv_w$上的一个等价类，那么它表示$\equiv_{wa}$上的一个等价类。这俩个类中的成员在一下情况下是不同的（意思是如果不满足这两个条件那么这两个集合是相同的）：$x \equiv_{w} \text{tail}(wa)$并且$\text{tail}(wa)$是在新的左上下文的第一次出现。在这种情况下，等价类$[x]_w$可以被划分为两类：词长超过$\text{tail}(wa)$保留在$[x]_{wa}$中，其他的划分进一个新类$[\text{tail}(wa)]_{wa}$，用$\text{tail}(wa)$表示。
- 在等价关系$\equiv_{wa}$上，除了1，2之外，再没有其他等价类。
说明：上述表示有点抽象，举个例子，比如从$abcb \to abcbc$，拓展前后的划分表示如下：
| 划分元素 | end-set | 代表元素 $x$ |
|---|---|---|
| a | 1 | a |
| ab | 2 | ab |
| c, bc, abc | 3 | abc |
| cb,bcb,abcb | 4 | abcb |
| b | 2,4 | b |
拓展后：
| 划分元素 | end-set | 代表元素 $x$ |
|---|---|---|
| a | 1 | a |
| ab | 2 | ab |
| abc | 3 | abc |
| cb,bcb,abcb | 4 | abcb |
| abcbc,bcbc,cbc | 5 | abcbc |
| b | 2,4 | b |
| c,bc | 3,5 | bc |
- 新增的等价类$[abcbc]_{wa}$包含了只在$abcbc$中出现的子串（相比拓展前多了${cbc, bcbc, abcbc}$三个子串）
- 拓展前的等价类$[abc]_w$在拓展后的串中分裂成了两个划分，分别是$[bc]_{wa}$和$[abc]_{wa}$。令$x = abc$，那么拓展前，有$abc \equiv_{w} bc$（因为$abc$和$bc$在划分$[abc]_w$中），拓展后，$\text{tail}(abcbc) = bc$而且$bc$在$abcbc$中满足新的左上下文的第一次出现。所以要对$[x]_w$，即$[abc]_w$进行分裂。分裂规则是：词长超过$bc$即2的${abc}$被划分进$[abc]_wa$中，其他的被划分进新的划分$[bc]_{wa}$中。其他不满足分裂条件的$x = {a, b, ab}$保持不变，$[x]_w = [x]_{wa}$。
上述过程定义了$D_w \to D_{wa}$的拓展过程，构造后缀自动机的思路是，首先一个字符一个字符的完成$D_W$的构造，之后再完成从$D_W \to M_W$的转换。
定义：
- 在$D_w$中，每个转移边要么是首要的，要么是次要的。
- 如果$xa = y$，那么从$x$代表的等价类到$y$代表的等价类的转移边就是首要的，否则就是次要的。
- 每个状态（除了初始状态）都有一个后缀指针，记录它在$T(w)$中的父节点。
- 如果$x$表示一个等价类，那么用$SC(x)$表示从$x$开始的后缀链。它是一条从$x$到$T(w)$根节点的路径。
那么
- 在等价关系$\equiv_{w}$上可以表示等价类的任何子串$x$，$SC(x)$都将$x$的后缀划分成了$|SC(x)|$类。
- 如果$w \ne \epsilon$，那么$D_w$宿节点的后缀节点指向$[\text{tail}(w)]_w$
- 回溯从$D_w$的宿节点到源节点的后缀指针过程中，遇到的第一个含有$a$的转移的等价类肯定有一个到$[\text{tail}((wa))]_w$的$a$转移。如果没有遇到$a$转移，那么$a$只在$wa$中出现一次，因此$\text{tail}(wa) = \epsilon$。
- 令$\text{tail}(wa) = xa$，那么$x$表示$\equiv_w$上的一个等价类，而且当且仅当从$[x]_w$到$[xa]_{w}$存在次要边的时候，$\text{tail}(wa)$是在左上下文的第一次出现。
设计以上定义的目的是：
- 在$D_w \to D_{wa}$过程中，后缀指针可以定义具体哪一个等价类需要分裂。
- 通过次要转移的存在可以确认该等价类是否需要被分裂。
下面给出$abc \to abcb \to abcbc$的拓展过程：
上图中蓝色线条表示后缀指针，虚线表示次要边，实线表示首要边，宿节点默认为上一次拓展操作中添加的节点。
算法核心在于拓展节点和分裂节点两步，对于每一个新增字符$a$，拓展节点时，操作如下：
- 新建一个节点$s$，建立一条从宿节点$e$到$s$的首要边，label为$a$。
- 确定新建节点的后缀节点。从宿节点开始，沿着后缀节点一路回溯（经过的节点称为回溯节点），直到到达源节点（$0$号节点)或者后缀节点被确定时停止，分为以下三种情况处理：
2.1 回溯节点没有label为$a$的边，那么新建一条到$s$的次要边
2.2 回溯节点有一条label为$a$的首要边，那么$s$的后缀节点就是这条边的指向
2.3 回溯节点有一条label为$a$的次要边，那么对这条边上的父子节点执行分类操作，分裂的新状态就是$s$的后缀节点 - 如果回溯完成，后缀节点还没确定，就设为源节点
- $s$成为新的宿节点
分裂操作如下，对于父子节点$p, s$：
- 新建一个子状态$c$
- 将$p \to s$的次要边，更改为$p \to c$的首要边
- 对于$s$所连接的节点，建立$c$到他们的次要边，label为$a$
- $c$的后缀节点更改为$s$的后缀节点，$s$的后缀节点更改为$c$
- 从父节点$p$开始回溯，直到到达源节点。如果回溯节点存在和$s$的次要边，将它改为到$c$的次要边，继续回溯，否则停止回溯。
以上图作为分析
对于$\text{split}(0, 2)$：
对于$\text{split}(5, 3)$：
以上仅仅是完成了$D_w$的在线构造，但是$D_w$还有简化的空间，后续还有相应的算法完成$D_w \to M_w$的转换，代码照着伪代码的思路写就行了，相比理论而言，简洁很多。