Part 0 SAM
§ 0.1 SAM的由来
SAM是什么？
短点儿的答案：SAM是把特定节点捏在一起的后缀树。
长点儿的答案：
先定义个有用的东西：
终点集：一个长长的字符串有很多子串，一个子串可能会在母串不同的位置出现很多次，这些出现位置的终点的集合叫做终点集。某个子串 \(S\) 的终点集记作 \(endpos(S)\) .
这个东西能引出来三个定理：
- 两个终点集相同当且仅当一个子串是另一个的后缀。
- 两个终点集要么包含，要么相离，不可能相交一部分。
- 对于一个终点集，这里面包含的所有子串的长度一定覆盖一个连续区间。
证明：
- 不然呢？对于一组终点来说，在这里结束的两个长度不同的串肯定有一方是另一方的后缀。
- 如果两个终点集有交，由上面的定理可得其中一个对应的子串必然为另一个的后缀，那么长点的那个一旦出现，短点的那个也会在同一位置上出现，不可能有某个位置仅为长串的终点而不是短串的终点。
- 对于一个子串而言，它的后缀的终点集大小不会小于他，因此得证。（也就是说如果长子串的某个后缀可以在别的地方有一个终点，那么比这个后缀更短的后缀也会在这个地方出现，不可能又回到一开始长子串的终点集）
根据上面的证明3，我们再定义一个比较有用的东西：后缀链接。
具体来说，对于一个子串，我们不断把它缩短（删去首字符），那么这个串的终点集大小一定是单调不降的，换句话说，去掉这个串的第一个字符时，终点集的大小要么不变要么变多。对于每一次集合大小的扩充，我们从之前的终点集画一条出边连到这个新的终点集。这条出边就叫做后缀链接。
他有这么两个性质：
- 所有后缀链接必定形成一棵树。
- 后缀链接形成的树一定也是终点集形成的树（母集合连向每一个子集）。
第一点的证明很简单，因为后缀链接只从较小的终点集连向较大的终点集，所以一定会形成一棵树。后者就更不用证明了。
还有最后一个东西要定义：
我们把所有终点集完全相同的子串放在一起，称作一个后缀等价类。这是一个非常关键的概念（刚刚构建的那棵后缀链接树中的节点就是一个后缀等价类）。
现在来说说什么是SAM吧！
后缀自动机是一张图，其中有一个初始状态，从这个点走出的任意一条路径都对应着原字符串的一个子串，并且SAM是满足上述条件的图中最小的一个。
看到这个条件，我们首先会想到后缀树对吧。毕竟一个子串就是一个后缀的一个前缀，后缀树上的一条根链就是后缀的一个前缀。但是后缀树不一定满足上面所说的最小性。
为什么呢？假如说有一个子串 A 和另一个子串 B，并且【这两个子串在后缀树上对应的子树】的结构是完全相同的，那么可以把这两个节点捏在一起，使他们共用同一个子树，而依然满足从根开始的任意一条路径都是一个子串的性质。
那么怎么样构建一个满足最小性的图呢？
容易想到一种思路，把后缀树的所有能捏的节点捏在一起，最后得到的DAG一定满足最小性。
证明：假如不满足最小性，那么就等于说有两个点，它们本来可以写为同一个点，但是分开了。考虑两点能写为同一个点的充要条件是从这两个点出发的所有路径都相同，而这样的两个点正好是可以捏到一起的。
那么这张DAG上的节点有什么意义呢？
考虑在原来的后缀树上，“从一个点 \(x\) 开始，往它的子树里面走”这个动作在原字符串上代表什么？当然代表的是从【 \(Rootchain(x)\) 所对应的子串】在原串中的终点集里的某个位置开始，在原串上往后走。
感性理解一下，“在原串上向后走”和“在后缀树上向下走”两个动作是一致的。
那么如果有两个节点 \(A,B\)，他们的子树完全相同，这意味着什么呢？
没错，从 \(A\) 或 \(B\) 出发，能得到的子串完全相同。结合上面关于终点集的论述，刚刚这句话也可以表述为：
【从 \(endpos(Rootchain(A))\) 中的每个位置出发，向后走任意长度的过程中，你的足迹标出的所有子串组成的集合】与【从 \(endpos(Rootchain(B))\) 中的每个位置出发，向后走任意长度的过程中，你的足迹标出的所有子串组成的集合】这两个集合是完全相同的。
而这只对应了一种可能—— \(endpos(Rootchain(A)) = endpos(Rootchain(B))\) .
没错！融合后的节点正是一个后缀等价类！
这里注意一下，实际情况下可能有三个或者更多节点融合为一个。
进一步可以推出，所有能融合的节点融合完毕后，新图恰好包含了所有后缀等价类。
正好，我们可以把前面提到的“后缀链接树”叠加到这张图上，这样图里面有了两类边：来自后缀树的转移边，和来自后缀链接的后缀链接边。
这个东西就是SAM了！
每个点需要维护这些东西：
- 这个后缀等价类的最小、最长子串长度 \(minlen(x)\) 和 \(maxlen(x)\) .
- 这个点在后缀链接树上的父子节点。
- 这个点的入边和出边。
并且还有四个性质：
- 对于SAM中的一条转移边 \((u,v)\)，一定有 \(maxlen(v) > maxlen(u)\) .
- 对于一条转移边 \((u,v)\)，【\(u\) 所对应的终点集】包含【\(v\) 所对应的终点集】.
- 沿着后缀链接树往上走， \(maxlen(u),minlen(u)\) 递减，且 \(minlen(u) = maxlen(fa(u))+1\) .
- 仅有一个点入度为零，仅有一个点出度为零。
证明：
- 考虑【被捏到 \(u\) 里面的所有原后缀树点】组成的集合，一个【被捏进 \(v\) 里面的原后缀树点】一定是这个集合里某个点的儿子。所以对于 \(u\) 中的每一种子串长度，\(v\) 中都一定有一个更长的与之对应。
- 一旦加了一个字符之后的字符串出现，那么少了一个的也必定出现。
- 根据后缀链接树构建方法易证。
- 根据构造方法易证。
§ 0.2 SAM的构建
一般采用增量构建的方法来构造SAM，具体来说就是每次在原字符串后面新增一个字符，并对SAM进行调整。
假设我们新插入的字符为 \(c\)，下面详细解释一下算法步骤：
如果是一棵后缀树的话，增量更新是简单的：对于每一个原串的每一个后缀所对应的点，在这里新增一个字符为 \(c\) 的转移，链接到一个新建的状态。
但如果是后缀自动机的话，那些需要添加新转移的点应该是满足【对应的终点集含有“原串尾”这个位置】的所有点。
这些点在哪里呢？在后缀链接树上【表示整个字符串的点】的根链里。
考虑到这一点，我们可以知道算法的前两步：
- 找到原先DAG中对应“整个原串”的那个节点 \(x\)，在它后面添加一个字符为 \(c\) 的转移，链接到我们新建的一个状态（暂且叫他 \(cur\)）。顺便初始化 \(maxlen(cur) = n+1,minlen(cur) = minlen(x)+1\) .
\(n\) 是添加新字符前原串的长度。
- 我们不断通过 \(x\) 的后缀链接往上跳，假如说跳到的这个点 \(p\) 还没有字符为 \(c\) 的转移，就直接连一条出边到 \(cur\) 这个点，并令 \(minlen(cur) = minlen(p) + 1\) .
注意此时还不能确定 \(link(cur)\) 指向哪里。
但是如果 \(p\) 本身就有了一个字符为 \(c\) 的转移该怎么办呢？假设这个转移到的点为 \(q\)，我们考虑两种情况：
-
\(maxlen(q) = maxnlen(p) + 1\)：这种情况下，我们知道 \(q\) 对应的终点集正好就是【 \(p\) 对应的终点集中的每一个位置】在原串上向右移动一个位置得到的。
而既然都这样了，那么我们直接在 \(q\) 的终点集里面塞一个 \(n+1\) 也没有什么不妥。所以直接令 \(link(cur) = q,minlen(cur) = maxlen(q)+1\)，然后退出算法。
为什么直接退出？因为这种情况下， \(p\) 在后缀链接树上的祖先也一定都有一个字符为 \(c\) 的转移，连向 \(q\) 在后缀链接树上的某个祖先。
-
\(maxlen(q) > maxnlen(p) + 1\)：因为我们是按照 \(maxlen\) 从大到小遍历 \(p\) 的，所以遇到这种情况时，对于任意一个【比 \(maxlen(p)\) 更长的原串后缀】这个子串，它在其他地方出现的时候，后一个位置绝不会是 \(c\) .
因此，\([n-maxlen(q),n+1]\) 这个子串与任意一个形如 \([x-maxlen(q)+1,x]\) 的子串都绝不相同。，也就是说包含 \([n-maxlen(p),n+1]\) 这个子串的点的 \(maxlen\) 一定是 \(maxlen(p)+1\) .
综上，我们需要把 \(q\) 这个状态裂成两半：\(t,q'\) . 二者的出边完全相同，但是 \(minlen,maxlen,link\) 改为如下量：
\[\begin{gather*} \begin{cases} minlen(t) = minlen(q)\\ maxlen(t) = maxlen(p)+1\\ link(t) = link(q) \end{cases} \\ ~ \\ \begin{cases} minlen(q') = maxlen(p+2)\\ maxlen(q') = maxlen(q)\\ link(q') = t \end{cases} \end{gather*} \]然后我们令 \(link(cur) = t\)，并遍历 \(p\) 在后缀链接树上的祖先，一旦有祖先有连向原来 \(q\) 的转移，就把这个转移重定向到 \(t\)。最后退出算法。