后缀自动机的相关概念

后缀自动机： 后缀自动机是用来存储某一个字符串的所有子串的一个有限状态自动机。如果我们想把一个字符串的所有子串存下来，就可以用后缀自动机，而后缀自动机则恰好可以将一个字符串的所有子串存储起来。自动机简称为 $DFA$，一个自动机会有一个源点和若干个终点。后缀自动机简称 $SAM$。

$DFA$ 可以看作一个有向无环图，类比于 $Trie$ 字典树。这里给出一张 $SAM$ 的例图。

后缀自动机的性质：

1. $SAM$ 是个状态机，一个起点，若干个终点，原串的所有子串和从 $SAM$ 起点开始的所有路径一一对应，不重不漏。所有终点就是包含后缀的点。

2. 每个点包含若干个子串，每个子串都一一对应一条从起点到该点的路径，且这些子串一定是里面最长的子串的连续后缀。

3. $SAM$ 问题中经常考虑两种边：

   1. 普通边，类似于 $Trie$，表示在某个状态所表示的所有子串的后面添加一个字符。
   2. $Link, Father$，表示从某个状态的终点向该状态所表示的最短子串的首字母删去后的字符串对应的状态的终点连边，这类边构成一棵树。

可以发现普通边是在后面加上一个字母，$Link, Father$ 是在前面删掉一个字母。

后缀自动机的构造思路：

我们定义一个函数 $endpos(s)$，表示子串 $s$ 所有出现位置（尾字母下标）的集合。对于所有子串，可能存在某些子串的 $endpos$ 的集合是完全相同的，我们称这些子串为一个 $endpos$ 的等价类。最终所有 $endpos$ 的等价类就是原图里的每个状态。我们将每个等价类表示成一个状态，我们就可以通过构造得到一个满足以上三个性质的后缀自动机。

首先看一下 $endpos$ 等价类满足的性质：

1. 令 $s1, s2$ 为 $S$ 的两个子串，不妨设 $\vert s1 \vert \leq \vert s2 \vert$（我们用 $\vert s \vert$ 表示 $s$ 的长度，此时等价于 $s1$ 不长于 $s2$），则 $s1$ 是 $s2$ 的后缀当且仅当 $endpos(s1) \supseteq endpos(s2)$，$s1$ 不是 $s2$ 的后缀当且仅当 $endpos(s1) \cap endpos(s2) = \emptyset$

2. 两个不同子串的 $endpos$，要么有包含关系，要么没有交集。

3. 两个子串的 $endpos$ 相同，那么短串为长串的后缀。

4. 对于一个状态 $st$（等价类），以及任意的 $longest(st)$ 的后缀 $s$，如果 $s$ 的长度满足：$\vert shortest(st) \vert \leq \vert s \vert \leq \vert longest(st) \vert$，那么 $s \in substrings(st)$

此时我们知道对于某一个等价类中包含的所有子串都一定是最长串的连续后缀，从前面的图中以 $endpos(x) = 4$ 的等价类为例此时，等价类中有 $aabb, abb,bb$，而更短的后缀 $b$ 就不再属于 $4$ 这个等价类了，因为 $b$ 可能会在其他 $4$ 以外的地方出现过，因此再短的话它的 $endpos$ 中可能会出现一些新的位置，因此再短后缀就会变成一个新的状态，新的状态里面存的字符串也一定是新串的若干个连续后缀，再变短又会变成新的状态，新的状态又包含更短的若干个连续后缀，以此类推。此时对于一个子串来说，他的后缀连续的来看的话，第一段属于第一个状态，小到某个程度从第二段开始就属于第二个状态，再小到某个程度从三段开始就属于第三个状态，以此类推，此时 $Link,Father$ 这类的边其实就是每个状态连向下一个状态的边。这就是这类边的意义。

而普通边，就是某个状态中的每个后缀后面都加上一个字母，变成一个新的状态，这就是普通边的意义。可以发现两类边其实都是连接不同的状态之间的边。

$SAM$ 可以处理一些问题。

对于如何求不同子串的数量，由于后缀自动机中从起点开始的每一条路径和原串的每一个子串是一一对应的关系，而且不同路径对应不同子串，没有重复，因此不同点之间表示的串一定是没有任何交集的，因此不同子串的集合就一定是不同点所表示的字符串的并集，我们只要能求出每个点所表示的字符串的数量，就能求出不同子串的数量。那么怎么求每个点所表示的字符串的数量呢，根据前面 $endpos$ 的性质 $4$，对于每个点所对应的字符串，我们找出最长的子串和最短的子串，他们之间的所有字符串就是该点的所有字符串，若最长子串长度为 $a$，最短子串长度为 $b$，那么该点的字符串数量就是 $a-b+1$。而每个点的最长串和最短串是可以在构造后缀自动机的过程中顺带进行维护的。而我们其实只需要维护最长串即可，由于所有的等价类合在一起是连续的后缀，因此对于要想求当前点的最短串，只需要找到当前点的 $Link,Father$ 边连向的下一个等价类的最长串 $c$，此时当前点的最短串就是 $a-c+1$

对于如何求每个子串出现的次数，假设要求子串 $s$ 出现的次数，其实就是求 $\vert endpos(s) \vert$，这里我们对于某一个等价类，我们去看一下连向它的 $Link,Father$ 边的等价类，这些等价类对应的串去掉首字母其实就是当前等价类对应的串，而根据前面的性质，我们知道这些等价类之间是相互没有交集的，因此这些等价类一定能拼在一起凑成当前等价类的一部分，但是并不能完全凑成当前等价类，因为如果当前等价类中的某些串并不能在前面加上一个字符，那么就不存在指向它的等价类，也就没有拼凑出它，而不能在前面加上字符的字符串只可能是某一个前缀，因此当前等价类中的字符串数量也就是 $\vert endpos(s) \vert$ 就等于所有指向它的等价类的 $endpos$ 的数量之和再加上当前等价类中的前缀数量。这是一个递推出结果的过程。这里注意，由于不同前缀的终点一定是不一样的，因此不同前缀一定属于不同的等价类，而且每一个等价类中最多只会有一个前缀，因此只需要在递推之前将所有有前缀的等价类加上一个 $1$，然后再去递推即可。

而要想找一下某一个子串在哪个等价类中，这个其实非常简单，只需要跟 $Trie$ 字典树一样从源点往下一个字母一个字母的走即可，最终走到的位置所在的点就是所在的等价类。

后缀自动机的构造过程：

构造的过程是一个增量式的加入的过程。

假设最开始自动机是空的，只有一个源点，源点表示空串，每次添加一个字符到自动机中，然后维护一遍，然后再添加下一个字符，再维护一遍，直到加入所有的字符为止。

对于每次要插入的字符 $c$，都要分情况来讨论，对于自动机中的每个状态我们需要维护一些信息，当前状态中所有子串的最大长度 $len$，当前状态 $Link$ 边指向的状态 $fa$，当前状态后面加上字符 $i$ 变成的新状态 $ch_i$。

我们设上一个插入的状态是 $p$，当前插入的状态是 $np$，此时显然 $np$ 的最大子串长度就是 $p$ 的最大子串长度 $+1$，然后由于 $p$ 的后面加上了 $c$，因此 $p$ 去掉首字母的状态后面也应该加上 $c$，因此将 $p$ 的 $Link$ 边指向的状态后面也加上 $c$，以此类推，需要将沿着 $Link$ 边往后走到的所有状态后面都加上 $c$。

如果中间某一个状态 $sq$ 后面已经有 $c$ 了，假设状态 $sq$ 加上 $c$ 后是状态 $q$，那么此时状态 $q$ 应该属于一个新的等价类，因此 $np$ 的 $Link$ 边应该指向 $q$，如果 $q$ 的长度是 $sq$ 的长度 $+1$，则我们直接令 $np$ 的 $Link$ 边直接指向 $q$。但是如果 $q$ 是长度不是 $sq$ 的长度 $+1$，则说明 $q$ 并不是跟在 $sq$ 后面的状态，因此我们需要复制一个真正跟在 $sq$ 后面的状态 $nq$，我们令 $nq$ 的长度是 $sq$ 的长度 $+1$，此时 $nq$ 就跟在 $sq$ 后面了，此时我们令 $q, np$ 的 $Link$ 边都指向 $nq$，然后要将 $sq$ 后面所有的状态的 $c$ 边如果指向 $q$，一律都改成指向 $nq$，到此字符 $c$ 就添加完毕。再用同样的方式继续添加后续字符即可

注意，后缀自动机构造的时候需要用到两倍的点，因此空间需要开两倍。

后缀自动机的时间复杂度：

后缀自动机的状态数量不会超过 $O(2n)$，自动机内转移的数量不会超过 $O(3n)$，和后缀自动机的时间复杂度就和状态数量、转移数量有关，因此后缀自动机的时间复杂度是 $O(n)$，这里不详细讲解后缀自动机的构造证明和时间复杂度证明，可以自行翻阅文献了解。