后缀自动机 (SAM)

字符串 $s$ 的两个非空子串 $u$ 和 $w$（假设 $\left|u\right|\le \left|w\right|$）的 $\mathrm{endpos}$ 相同，当且仅当字符串 $u$ 在 $s$ 中每次出现时，都是以 $w$ 后缀的形式存在的。

引理显然成立。如果 $u$ 和 $w$ 的 $\mathrm{endpos}$ 相同，则 $u$ 是 $w$ 的一个后缀，且在 $s$ 中只以 $w$ 的后缀的形式出现。反过来，根据定义，如果 $u$ 为 $w$ 的一个后缀，且只以 $w$ 的后缀的形式在 $s$ 中出现，那么两个子串的 $\mathrm{endpos}$ 相同。

考虑两个非空子串 $u$ 和 $w$（假设 $\left|u\right|\le \left|w\right|$）。那么，要么 $\mathrm{endpos}(u)\cap \mathrm{endpos}(w)=\varnothing$，要么 $\mathrm{endpos}(w)\subseteq \mathrm{endpos}(u)$，取决于 $u$ 是否为 $w$ 的一个后缀：

$$\{\begin{array}{ll}\mathrm{endpos}(w)\subseteq \mathrm{endpos}(u),& \text{if }u\text{ is a suffix of }w,\\ \mathrm{endpos}(w)\cap \mathrm{endpos}(u)=\varnothing ,& \text{otherwise}.\end{array}$$

如果集合 $\mathrm{endpos}(u)$ 与 $\mathrm{endpos}(w)$ 有至少一个公共元素，那么由于字符串 $u$ 与 $w$ 在相同位置结束，$u$ 是 $w$ 的一个后缀。所以在每次 $w$ 出现的位置，子串 $u$ 也会出现。所以 $\mathrm{endpos}(w)\subseteq \mathrm{endpos}(u)$。

考虑一个 $\mathrm{endpos}$ 相同的子串等价类，将类中的所有子串按长度非递增的顺序排序。那么，每个子串都不会比它前一个子串长，与此同时每个子串也是它前一个子串的后缀。换句话说，对于同一等价类的任意两子串，较短者为较长者的后缀，且该等价类中的子串长度是连续的，取遍某个区间内的所有整数值。

如果等价类中只包含一个子串，引理显然成立。现在我们来讨论子串元素个数大于 $1$ 的等价类。

由引理 1，$\mathrm{endpos}$ 相同的两个不同字符串中，必定一长一短，且较短者总是较长者的真后缀。也就是说，等价类中没有等长的字符串。

记 $w$ 为等价类中最长的字符串，$u$ 为等价类中最短的字符串。由引理 1，字符串 $u$ 是字符串 $w$ 的真后缀。现在考虑长度在区间 $[\left|u\right|,\left|w\right|]$ 中的 $w$ 的任意后缀。容易看出，这个后缀也在同一等价类中，因为这个后缀只能在字符串 $s$ 中以 $w$ 的一个后缀的形式存在（这是因为较短的后缀 $u$ 在 $s$ 中只以 $w$ 的后缀的形式存在）。因此，由引理 1，这个后缀和字符串 $w$ 的 $\mathrm{endpos}$ 相同。

所有后缀链接构成一棵根节点为 $t_0$ 的树。

考虑任意状态 $v\ne t_0$，后缀链接 $\mathrm{link}(v)$ 连接到的状态对应于严格更短的字符串（后缀链接的定义、引理 3）。因此，沿后缀链接移动，我们总是能到达对应空串的初始状态 $t_0$。

以 $\mathrm{endpos}$ 集合为结点、集合的包含关系作为边，这样构造的树（即每个子节点的 $\mathrm{endpos}$ 集合都包含在父节点的 $\mathrm{endpos}$ 集合中）与通过后缀链接 $\mathrm{link}$ 构造的树相同。

由引理 2，任意一个 SAM 的 $\mathrm{endpos}$ 集合形成了一棵树（因为两个集合要么完全没有交集要么其中一个是另一个的子集）。

我们现在考虑任意状态 $v\ne t_0$ 及后缀链接 $\mathrm{link}(v)$，由后缀链接和引理 2，我们可以得到

$$\mathrm{endpos}(v)⊊\mathrm{endpos}(\mathrm{link}(v)).$$

注意这里应该是 $⊊$ 而不是 $\subseteq$，因为若 $\mathrm{endpos}(v)=\mathrm{endpos}(\mathrm{link}(v))$，那么 $v$ 和 $\mathrm{link}(v)$ 应该被合并为一个结点。

在字符串 $s$ 的 SAM 的基础上，可以构造字符串 $s+c$ 的 SAM。根据前文对图示的解释，只需要构造出新增加的前缀（即 $s+c$）的后缀路径，并压缩到现有的路径上即可。而且，根据前文的描述，新的后缀路径上的结点必然都可以通过原字符串 $s$ 的后缀路径上的结点经由字符 $c$ 转移而来。

我们首先考虑在添加新字符 $c$ 之前，原来的字符串 $s$ 的后缀路径可能具有什么形式，而且会怎样经由字符 $c$ 转移。最一般的情形，如下图示：

图中，原字符串 $s$ 的后缀路径为 $p_0\to p_1\to \cdots \to p_6\to t_0$，后缀链接由红色箭头表示。其中部分结点（即 $p_2\sim p_6$）已经存在经由字符 $c$ 的转移；因为将连续的后缀串添加同一个字符会同样得到连续的后缀，所以这些转移的终点组成另一串后缀路径 $q_1\to q_2\to q_3\to t_0$。此时，有两点观察：

• 原字符串 $s$ 的后缀路径上，没有经由 $c$ 的转移的结点一定是最初的几个结点。只要从某个结点（图中的 $p_2$）开始，存在经由 $c$ 的转移，后续经过的结点也一定存在经由 $c$ 的转移。

  解释：设 $s_2=\mathrm{longest}(p_2)$，那么后续经过的所有结点都对应 $s_2$ 的后缀，因而如果 $s_2+c$ 也出现在 $s$ 中，那么 $s_2$ 的后缀再加 $c$ 的结果也一定出现在 $s$ 中，因此这些结点都有经由 $c$ 的转移。

• 虽然经由字符 $c$ 能够到达结点 $q_i$ 的结点一定是后缀链接树上的连续段，但是这个连续段未必全体都位于自 $p_0$ 到根的后缀路径上。特别地，只有第一个结点 $q_1$ 对应的连续段中起始的若干个结点 可能 不在这个后缀路径上。例如图中的结点 $q_1$ 就对应结点 $p_1^{\prime }\to p_2\to p_3$，其中，$p_1^{\prime }$ 不在 $p_0$ 的后缀路径上。

  解释：设 $s_2=\mathrm{longest}(p_2)$，则 $s_2+c$ 对应着 $q_1$，但是图中显然有 $s_2+c\ne \mathrm{longest}(q_1)$，因为后者是 $\mathrm{longest}(p_1^{\prime })+c$。这就说明，$q_1$ 对应的部分字符串不能由 $s_2$ 及其后缀转移来。反过来，$q_2$ 中的字符串必然是 $s_2+c$ 的后缀，因此删去末尾的 $c$ 后必然是 $s_2$ 的后缀。也就是说，经由 $c$ 转移到 $q_2$ 的结点必然在 $p_2$ 起始的后缀路径上。这也是为什么只有起始的 $q_1$ 对应的连续段中的部分结点可能不在 $p_0$ 的后缀路径上。

对于这个图示，如果要在原字符串 $s$ 的末尾添加一个字符 $c$，并构造出相应的后缀路径，会发生什么变化呢？答案是如下图所示：

因为结点 $q_0$ 由原字符串 $s$ 对应结点 $p_0$ 经由字符 $c$ 转移而来，它就对应新字符串 $s+c$。所以，它的后缀路径 $q_0\to q_1^{″}\to q_2\to q_3\to t_0$ 就是新增的后缀路径。如果原来的后缀路径上的结点 $p_i$ 本就有经由 $c$ 的转移，那么新的后缀路径也必然会经过这些转移到达的结点，因此可以直接复用旧有的结点。新的后缀路径上有且只有一个完全新建的节点 $q_0$，用于接受原来的后缀路径上起始的那些没有经由 $c$ 的转移的结点的转移。

除了这些显然的事实外，还可以注意到，原来的结点 $q_1$ 也经过了一次复制，或者说是分裂成了两个结点 $q_1^{\prime }\to q_1^{″}$。这是因为新增的后缀路径只是与现有路径部分重合：原来的结点 $q_1$ 对应的字符串中，只有较短的那些（即结点 $p_2$ 和 $p_3$ 能够转移到的那些）才会出现在新增的后缀路径上，而较长的那些（即结点 $p_1^{\prime }$ 能够转移到的那些）并不会出现在新增的后缀路径上，因此新增的后缀路径只能经过结点 $q_1$ 的一部分，后者只能分裂成两个结点用于表示这种情形。同样的道理，前面已经解释过，$q_1$ 之后的结点 $q_2$ 和 $q_3$ 都无法由不在 $p_0$ 的后缀路径上的结点转移，因此这些结点对应的所有字符串都会出现在新增的后缀路径上，也就不需要分裂了。

从 SAM 中状态代表的含义看，每个状态都是一个 $\mathrm{endpos}$ 集合。设延长字符串时，新增的结束位置为 $i$，那么新增的结点 $q_0$ 就是结束位置集合 $\{i\}$，而分裂的结点 $q_1^{\prime }$ 和 $q_1^{″}$ 分别对应集合 $\mathrm{endpos}(q_1)$ 和 $\mathrm{endpos}(q_1)\cup \{i\}$，之后的结点 $q_2$ 和 $q_3$ 其实都在原有的结束位置集合上新增了 $i$。也就是说，虽然 $q_2$ 和 $q_3$ 及其相关的转移没有发生变化，但是它们对应的 $\mathrm{endpos}$ 集合的确扩大了。

以上说明的是最复杂、最一般的情形（即下文的 情形三）。实际操作时，可能并不存在结点 $p_1^{\prime }$，因而也就不需要分裂（即下文的 情形二）。要判断这种情形，只需要判断 $\mathrm{longest}(q_1)=\mathrm{longest}(p_2)+c$ 即可，亦即 $\mathrm{len}(q_1)=\mathrm{len}(p_2)+1$。也有可能 $p_0$ 的后缀路径上的所有结点都没有经由 $c$ 的转移，此时，只要新建 $q_0$ 就好了（即下文的 情形一）。

• 令 $\mathit{\text{last}}$ 为添加字符 $c$ 之前，整个字符串对应的状态（一开始我们设 $\mathit{\text{last}}=0$，算法的最后一步更新 $\mathit{\text{last}}$）。
• 创建一个新的状态 $\mathit{\text{cur}}$，并将 $\mathrm{len}(\mathit{\text{cur}})$ 赋值为 $\mathrm{len}(\mathit{\text{last}})+1$，在这时 $\mathrm{link}(\mathit{\text{cur}})$ 的值还未知。
• 现在我们进行如下流程：从状态 $\mathit{\text{last}}$ 开始，如果当前状态还没有标号为字符 $c$ 的转移，我们就添加一个经字符 $c$ 到状态 $\mathit{\text{cur}}$ 的转移，并将当前状态沿后缀链接移动。如果过程中遇到某个状态已经存在到字符 $c$ 的转移，我们就停下来，并将这个状态标记为 $p$。
• 情况一：如果没有找到这样的状态 $p$，我们就到达了虚拟状态 $-1$，我们将 $\mathrm{link}(\mathit{\text{cur}})$ 赋值为 $0$ 并退出。
• 假设现在我们找到了一个状态 $p$，它可以通过字符 $c$ 转移。我们将转移到的状态标记为 $q$。此时，要么 $\mathrm{len}(p)+1=\mathrm{len}(q)$，要么 $\mathrm{len}(p)+1<\mathrm{len}(q)$。
• 情况二：如果 $\mathrm{len}(p)+1=\mathrm{len}(q)$，我们只要将 $\mathrm{link}(\mathit{\text{cur}})$ 赋值为 $q$ 并退出。

• 情况三：否则就会有些复杂，需要 复制 状态 $q$：我们创建一个新的状态 $\mathit{\text{clone}}$，复制 $q$ 的除了 $\mathrm{len}$ 的值以外的所有信息（后缀链接和转移）。我们将 $\mathrm{len}(\mathit{\text{clone}})$ 赋值为 $\mathrm{len}(p)+1$。

  复制之后，我们将后缀链接从 $\mathit{\text{cur}}$ 指向 $\mathit{\text{clone}}$，也从 $q$ 指向 $\mathit{\text{clone}}$。

  最终我们需要沿着后缀链接从状态 $p$ 往回走，只要经过的状态存在指向状态 $q$ 的转移，就将该转移重新连接到状态 $\mathit{\text{clone}}$。

• 处理完以上三种情况后，我们都需要将 $\mathit{\text{last}}$ 的值更新为状态 $\mathit{\text{cur}}$。

• 若一个转移 $(p,q)$ 满足 $\mathrm{len}(p)+1=\mathrm{len}(q)$，则我们称这个转移是 连续的。否则，即当 $\mathrm{len}(p)+1<\mathrm{len}(q)$ 时，这个转移被称为 不连续的。

  从算法描述中可以看出，连续的和不连续的转移，在算法中的处理也并不相同。连续的转移是固定的，我们不会再改变了。与此相反，当向字符串中插入一个新的字符时，不连续的转移可能会改变（转移边的端点可能会改变）。

• 为了避免引起歧义，我们记向 SAM 中插入当前字符 $c$ 之前的字符串为 $s$。

• 算法从创建一个新状态 $\mathit{\text{cur}}$ 开始，对应于整个字符串 $s+c$。我们创建一个新的节点的原因很清楚。与此同时我们也创建了一个新的字符和一个新的等价类。

• 在创建一个新的状态之后，我们会从对应整个字符串 $s$ 的状态 $\mathit{\text{last}}$ 沿着后缀链接进行移动。对于经过的每一个状态，我们尝试添加一个通过字符 $c$ 到新状态 $\mathit{\text{cur}}$ 的转移。

  然而我们只能添加与原有转移不冲突的转移。因此我们只要找到已存在的 $c$ 的转移，我们就必须停止。

• 最简单的情况是我们到达了虚拟状态 $-1$，这意味着我们为所有 $s$ 的后缀添加了 $c$ 的转移。这也意味着，字符 $c$ 从未在字符串 $s$ 中出现过。因此 $\mathit{\text{cur}}$ 的后缀链接为状态 $0$。

• 第二种情况下，我们找到了现有的转移 $(p,q)$。这意味着我们尝试向自动机内添加一个 已经存在的 字符串 $x+c$（其中 $x$ 为 $s$ 的一个后缀，且字符串 $x+c$ 已经作为 $s$ 的一个子串出现过了）。因为我们假设字符串 $s$ 的自动机的构造是正确的，我们不应该在这里添加一个新的转移。

  然而，难点在于，从状态 $\mathit{\text{cur}}$ 出发的后缀链接应该连接到哪个状态呢？我们要把后缀链接连到一个状态上，且对应的最长的字符串恰好是 $x+c$，即这个状态的 $\mathrm{len}$ 应该是 $\mathrm{len}(p)+1$。然而这样的状态有可能并不存在，即 $\mathrm{len}(q)>\mathrm{len}(p)+1$。这种情况下，我们必须通过拆开状态 $q$ 来创建一个这样的状态。

• 当然，如果转移 $(p,q)$ 是连续的，那么 $\mathrm{len}(q)=\mathrm{len}(p)+1$。在这种情况下一切都很简单。我们只需要将 $\mathit{\text{cur}}$ 的后缀链接指向状态 $q$。

• 否则转移是不连续的，即 $\mathrm{len}(q)>\mathrm{len}(p)+1$，这意味着状态 $q$ 不只对应于长度为 $\mathrm{len}(p)+1$ 的后缀 $s+c$，还对应于 $s$ 的更长的子串。除了将状态 $q$ 拆成两个子状态以外我们别无他法，所以第一个子状态的长度就是 $\mathrm{len}(p)+1$ 了。

  我们如何拆开一个状态呢？我们 复制 状态 $q$，产生一个状态 $\mathit{\text{clone}}$，我们将 $\mathrm{len}(\mathit{\text{clone}})$ 赋值为 $\mathrm{len}(p)+1$。由于我们不想改变经过 $q$ 的路径，我们将 $q$ 的所有转移复制到 $\mathit{\text{clone}}$。我们也将从 $\mathit{\text{clone}}$ 出发的后缀链接设置为 $q$ 的后缀链接的目标，并设置 $q$ 的后缀链接为 $\mathit{\text{clone}}$。

  在拆开状态后，我们将从 $\mathit{\text{cur}}$ 出发的后缀链接设置为 $\mathit{\text{clone}}$。

  最后一步我们将一些原本指向 $q$ 的转移重新连接到 $\mathit{\text{clone}}$。我们需要修改哪些转移呢？只重新连接相当于所有字符串 $w+c$（其中 $w$ 是状态 $p$ 对应的最长字符串）的后缀就够了。也就是说，我们需要继续沿着后缀链接移动，从结点 $p$ 直到虚拟状态 $-1$，或者当前状态经 $c$ 的转移不再指向状态 $q$。

如果我们考虑算法的各个部分，算法中有三处时间复杂度不明显是线性的：

• 第一处是遍历所有状态 $\mathit{\text{last}}$ 的后缀链接，添加字符 $c$ 的转移。
• 第二处是当状态 $q$ 被复制到一个新的状态 $\mathit{\text{clone}}$ 时复制转移的过程。
• 第三处是修改指向 $q$ 的转移，将它们重新连接到 $\mathit{\text{clone}}$ 的过程。

我们使用 SAM 的大小（状态数和转移数）为 线性的 的事实（对状态数是线性的的证明就是算法本身，对转移数为线性的的证明将在稍后实现算法后给出）。

因此上述 第一处和第二处 的总复杂度显然为线性的，因为单次操作均摊只为自动机添加了一个新转移。

还需为 第三处 估计总复杂度，我们将最初指向 $q$ 的转移重新连接到 $\mathit{\text{clone}}$。我们记 $v=\mathrm{longest}(p)$，这是字符串 $s$ 的一个后缀。每迭代一次，$v$ 的长度都减小，因而 $v$ 作为 $s$ 的后缀的起始位置必然在后移。因此，循环中 $p$ 沿后缀链接移动的次数，不超过 $v$ 作为 $s$ 的后缀的起始位置向后移动的距离。因为 $p$ 至少要向后移动一次，才能终止循环，而且 $p$ 至少是 $last$ 沿后缀链接移动一次的结果，因此循环终止时，$v$ 作为 $s$ 的后缀的的起始位置并不比字符串 $\mathrm{longest}(\mathrm{link}(\mathrm{link}(\mathit{\text{last}}))$ 更靠前。而且，循环终止时，字符串 $v$ 作为 $s$ 的后缀的起始位置将恰好是 $v+c$ 作为 $s+c$ 的后缀的起始位置，而作为 $s+c$ 的后缀，字符串 $v+c$ 恰好是字符串 $\mathrm{longest}(\mathrm{link}(\mathrm{link}(\mathit{\text{cur}}))$。因为 $cur$ 是更新后的 $last$ 的值，所以循环中移动的次数不会超过更新前后 $\mathrm{longest}(\mathrm{link}(\mathrm{link}(\mathit{\text{last}}))$ 作为当前字符串后缀的起始位置向后移动的距离，再加一（即为了终止循环必须移动的次数）。

因为作为当前字符串后缀的字符串 $\mathrm{longest}(\mathrm{link}(\mathrm{link}(\mathit{\text{last}}))$ 的位置在整个 SAM 构造过程中单调递增³，它的总移动距离必然不超过 $n$。这就说明，需要修改指向 $q$ 的转移的循环中，迭代次数不超过 $2n$。这正是我们需要证明的。

算法本身即可证明该结论。一开始，自动机含有一个状态，第一次和第二次迭代中只会创建一个节点，剩余的 $n-2$ 步中每步会创建至多 $2$ 个状态。

然而我们也能在 不借助这个算法 的情况下 证明 这个估计值。我们回忆一下状态数等于不同的 $\mathrm{endpos}$ 集合个数。这些 $\mathrm{endpos}$ 集合形成了一棵树（父节点的 $\mathrm{endpos}$ 集合包含子节点的 $\mathrm{endpos}$ 集合）。考虑将这棵树稍微变形一下：只要它有一个只有一个子节点的内部节点（这意味着该子节点的集合至少遗漏了它的父节点的集合中的一个位置），我们就创建一个含有这些遗漏位置的集合作为它的子节点。最后我们可以获得一棵每一个内部结点的度数都大于一的树，且叶子节点的个数不超过 $n$。这样的树里有不超过 $2n-1$ 个节点，因此，原来的不同的 $\mathrm{endpos}$ 集合个数也不超过 $2n-1$。

字符串 $\mathtt{\text{abbb}}\cdots \mathtt{\text{bbb}}$ 的状态数达到了该上界：从第三次迭代后的每次迭代，算法都会拆开一个状态，最终产生恰好 $2n-1$ 个状态。

我们首先估计连续的转移的数量。考虑自动机中由从状态 $t_0$ 开始到达所有状态的最长路径组成的生成树。生成树只包含连续的边，因此数量少于状态数，即边数不会超过 $2n-2$。

现在我们来估计不连续的转移的数量。令当前不连续转移为 $(p,q)$，其字符为 $c$。我们取它的对应字符串 $u+c+w$，其中字符串 $u$ 对应于初始状态到 $p$ 的最长路径，$w$ 对应于从 $q$ 到任意终止状态的最长路径。一方面，每个不完整的字符串所对应的形如 $u+c+w$ 的字符串是不同的（因为字符串 $u$ 和 $w$ 仅由完整的转移组成）。另一方面，由终止状态的定义，每个形如 $u+c+w$ 的字符串都是整个字符串 $s$ 的后缀。因为 $s$ 只有 $n$ 个非空后缀，且形如 $u+c+w$ 的字符串都不包含 $s$（因为整个字符串只包含完整的转移），所以非完整的转移的总数不会超过 $n-1$。

将以上两个估计值相加，我们可以得到上界 $3n-3$。然而，最大的状态数只能在类似于 $\mathtt{\text{abbb}}\cdots \mathtt{\text{bbb}}$ 的情况中产生，而此时转移数量显然少于 $3n-3$。

因此我们可以获得更为紧确的 SAM 的转移数的上界：$3n-4$。字符串 $\mathtt{\text{abbb}}\cdots \mathtt{\text{bbbc}}$ 就达到了这个上界。

我们在 $O(\left|T\right|)$ 的时间内对文本串 $T$ 构造后缀自动机。为了检查模式串 $P$ 是否在 $T$ 中出现，我们沿转移（边）从 $t_0$ 开始根据 $P$ 的字符进行转移。如果在某个点无法转移下去，则模式串 $P$ 不是 $T$ 的一个子串。如果我们能够这样处理完整个字符串 $P$，那么模式串在 $T$ 中出现过。

对于每个字符串 $P$，算法的时间复杂度为 $O(\left|P\right|)$。此外，这个算法还找到了模式串 $P$ 在文本串中出现的最大前缀长度。

对字符串 $S$ 构造后缀自动机。

每个 $S$ 的子串都相当于自动机中的一些路径。因此不同子串的个数等于自动机中以 $t_0$ 为起点的不同路径的条数。

考虑到 SAM 为有向无环图，不同路径的条数可以通过动态规划计算。即令 $d_v$ 为从状态 $v$ 开始的路径数量（包括长度为零的路径），则我们有如下递推方程：

$$d_v=1+\sum _{w:(v,w,c)\in DAWG}{d}_w$$

即，$d_v$ 可以表示为所有 $v$ 的转移的末端的和，$DAWG$ 中的三元组 $(v,w,c)$ 表示后缀自动机中存在自 $v$ 经 $c$ 至 $w$ 的转移。

所以不同子串的个数为 $d_{t_0}-1$（因为要去掉空子串）。

总时间复杂度为：$O(\left|S\right|)$。

另一种方法是在构造完后缀自动机后，利用得到的后缀链接树的信息。每个节点对应的子串数量是 $\mathrm{len}(v)-\mathrm{len}(\mathrm{link}(v))$，对自动机所有节点求和即可。

总时间复杂度仍然为：$O(\left|S\right|)$。

本题做法与上一题类似，只是现在我们需要考虑分两部分进行动态规划：不同子串的数量 $d_v$ 和它们的总长度 $an{s}_v$。

我们已经在上一题中介绍了如何计算 $d_v$。$an{s}_v$ 的值可以通过以下递推式计算：

$$an{s}_v=\sum _{w:(v,w,c)\in DAWG}{d}_w+an{s}_w$$

我们取每个邻接结点 $w$ 的答案，并加上 $d_w$（因为从状态 $v$ 出发的子串都增加了一个字符）。

算法的时间复杂度仍然是 $O(\left|S\right|)$。

同样可以利用后缀链接树的信息。每个节点对应的最长子串的所有后缀长度是

$${\displaystyle \frac{\mathrm{len}(v)\times (\mathrm{len}(v)+1)}{2}},$$

减去其 $\mathrm{link}$ 节点的对应值就是该节点的净贡献，对自动机所有节点求和即可。

总时间复杂度仍然为：$O(\left|S\right|)$。

解决这个问题的思路可以从解决前两个问题的思路发展而来。字典序第 $k$ 大的子串对应于 SAM 中字典序第 $k$ 大的路径，因此在计算每个状态的路径数后，我们可以很容易地从 SAM 的根开始找到第 $k$ 大的路径。

预处理的时间复杂度为 $O(\left|S\right|)$，单次查询的复杂度为 $O(\left|ans\right|\cdot \left|\mathrm{\Sigma }\right|)$（其中 $ans$ 是查询的答案，$\left|\mathrm{\Sigma }\right|$ 为字符集的大小）。

容易发现字符串 $S+S$ 包含字符串 $S$ 的所有循环移位作为子串。

所以问题简化为在 $S+S$ 对应的后缀自动机上寻找最小的长度为 $\left|S\right|$ 的路径，这可以通过平凡的方法做到：我们从初始状态开始，贪心地访问最小的字符即可。

总的时间复杂度为 $O(\left|S\right|)$。

利用后缀链接树的信息，进行 dfs 即可预处理每个节点的 $\mathrm{endpos}$ 集合的大小。

所有「前缀节点」的初始集合大小为 $1$，非「前缀节点」的初始集合大小为 $0$。然后，沿着后缀链接自下向上回溯时，每个父节点的集合大小都加上它的所有子节点的集合大小（不要遗漏父节点本身的初始值）。这样得到的每个节点处的值，就是该节点的 $\mathrm{endpos}$ 集合的大小。不同子节点的集合大小可以直接相加的理由是，同一个 $v_i$ 只会出现在一个子树内，故而相加不会重复。

查询时，在自动机上查找模式串 $P$ 对应的节点，如果存在，则答案就是该节点的 $\mathrm{endpos}$ 集合的大小；如果不存在，则答案为 $0$。

预处理时间复杂度为 $O(|T|)$。单次查询的时间复杂度为 $O(|P|)$。

对文本串 $T$ 构造后缀自动机。

接下来做预处理：对于自动机中的每个状态 $v$，预处理 $cn{t}_v$，使之等于 $\mathrm{endpos}(v)$ 集合的大小。事实上，对应同一状态 $v$ 的所有子串在文本串 $T$ 中的出现次数相同，这相当于集合 $\mathrm{endpos}$ 中的位置数。

然而我们不能明确的构造集合 $\mathrm{endpos}$，因此我们只考虑它们的大小 $cnt$。

为了计算这些值，我们进行以下操作。对于每个状态，如果它不是通过复制创建的（且它不是初始状态 $t_0$），我们将它的 $cnt$ 初始化为 1。然后我们按它们的长度 $\mathrm{len}$ 降序遍历所有状态，并将当前的 $cn{t}_v$ 的值加到后缀链接指向的状态上，即：

$$cn{t}_{\mathrm{link}(v)}+=cn{t}_v$$

这样做每个状态的答案都是正确的。

为什么这是正确的？不是通过复制获得的状态，恰好有 $\left|T\right|$ 个，并且它们中的前 $i$ 个在我们插入前 $i$ 个字符时产生。因此对于每个这样的状态，我们在它被处理时计算它们所对应的位置的数量。因此我们初始将这些状态的 $cnt$ 的值赋为 $1$，其它状态的 $cnt$ 值赋为 $0$。

接下来我们对每一个 $v$ 执行以下操作：$cn{t}_{\mathrm{link}(v)}+=cn{t}_v$。其背后的含义是，如果有一个字符串 $v$ 出现了 $cn{t}_v$ 次，那么它的所有后缀也在完全相同的地方结束，即也出现了 $cn{t}_v$ 次。

为什么我们在这个过程中不会重复计数（即把某些位置数了两次）呢？因为我们只将一个状态的位置添加到 一个 其它的状态上，所以一个状态不可能以两种不同的方式将其位置重复地指向另一个状态。

因此，我们可以在 $O(\left|T\right|)$ 的时间内计算出所有状态的 $cnt$ 的值。

最后回答询问只需要查找值 $cn{t}_t$，其中 $t$ 为模式串对应的状态，如果该模式串不存在答案就为 $0$。单次查询的时间复杂度为 $O(\left|P\right|)$。

利用后缀链接树的信息，进行 dfs 即可预处理每个节点的 $\mathrm{endpos}$ 集合中的最小值。

所有「前缀节点」$v_i$ 的初始值为 $i$，非「前缀节点」的初始值为 $\mathrm{\infty }$。然后，沿着后缀链接自下向上回溯时，每个父节点的值都与它的所有子节点的值比较，取最小值（不要遗漏父节点本身的初始值）。这样得到的每个节点处的值，就是该节点的 $\mathrm{endpos}$ 集合中的最小值。

查询时，在自动机上查找模式串 $P$ 对应的节点，如果存在，则答案就是该节点的值，减去 $|P|-1$；如果不存在，则答案不存在。

预处理时间复杂度为 $O(|T|)$。单次查询的时间复杂度为 $O(|P|)$。

我们构造一个后缀自动机。我们对 SAM 中的所有状态预处理位置 $\mathrm{firstpos}$。即，对每个状态 $v$ 我们想要找到第一次出现这个状态的末端的位置 $\mathrm{firstpos}[v]$。换句话说，我们希望先找到每个集合 $\mathrm{endpos}$ 中的最小的元素（显然我们不能显式地维护所有 $\mathrm{endpos}$ 集合）。

为了维护 $\mathrm{firstpos}$ 这些位置，我们对函数 sam_extend() 进行扩展。当我们创建新状态 $\mathit{\text{cur}}$ 时，我们令：

$$\mathrm{firstpos}(\mathit{\text{cur}})=\mathrm{len}(\mathit{\text{cur}})-1.$$

当我们将结点 $q$ 复制到 $\mathit{\text{clone}}$ 时，我们令：

$$\mathrm{firstpos}(\mathit{\text{clone}})=\mathrm{firstpos}(q).$$

（因为值的唯一的其它选项 $\mathrm{firstpos}(\mathit{\text{cur}})$ 显然太大了）。

那么查询的答案就是 $\mathrm{firstpos}(t)-\left|P\right|+1$，其中 $t$ 为对应字符串 $P$ 的状态。单次查询只需要 $O(\left|P\right|)$ 的时间。

找到模式串 $P$ 对应的节点后，利用后缀链接树的信息，遍历子树，一旦发现终点节点就输出。

单次查询复杂度为 $O(|P|)+O(\mathit{\text{answer}}(P))$，其中，$\mathit{\text{answer}}(P)$ 为本次询问的答案。仿照 状态数为线性的证明 可以说明，后缀链接树的子树大小不会超过该节点的 $\mathrm{endpos}$ 集合的大小的二倍，因此遍历子树的复杂度是 $O(\mathit{\text{answer}}(P))$ 的。

我们还是对文本串 $T$ 构造后缀自动机。与上一个问题相似，我们为所有状态计算位置 $\mathrm{firstpos}$。

如果 $t$ 为对应于模式串 $P$ 的状态，显然 $\mathrm{firstpos}(t)$ 为答案之一。我们已经找到了自动机中对应于 $P$ 的状态。还需要找到其它哪些位置？正是那些对应于以 $P$ 为后缀的字符串的状态。换句话说，我们要找到所有可以通过后缀链接到达状态 $t$ 的状态。

因此为了解决这个问题，我们需要为每一个状态保存一个指向它的后缀连接列表。查询的答案就包含了对于每个我们能从状态 $t$ 只使用反向的后缀链接进行 DFS 或 BFS 找到的所有状态的 $\mathrm{firstpos}$ 值。

预处理的复杂度为 $O(|T|)$，单次查询的复杂度为 $O(|P|+\mathit{\text{answer}}(P))$。

我们不会重复访问一个状态（因为对于仅有一个后缀链接指向一个状态，所以不存在两条不同的路径指向同一状态）。

我们只需要考虑两个可能有相同 $\mathrm{firstpos}$ 值的不同状态。这种情形只在一个状态是由另一个状态复制而来时发生。然而，这并不会对复杂度分析造成影响。仿照 状态数为线性的证明，所有这种后缀为 $P$ 的状态数目不会超过 $2\mathit{\text{answer}}(P)$。

此外，我们可以通过不考虑复制而来的节点的 $\mathrm{firstpos}$ 值来去除重复的位置。事实上对于一个状态，如果经过被复制状态可以到达，则经过原状态也可以到达。因此，如果我们给每个状态记录标记 is_clone 来代表这个状态是不是被复制出来的，我们就可以简单地忽略掉被复制的状态，只输出其它所有状态的 $firstpos$ 的值。

以下是大致的实现：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

struct state {
  bool is_clone;
  int first_pos;
  std::vector<int> inv_link;
  // some other variables
};

// 在构造 SAM 后
for (int v = 1; v < sz; v++) st[st[v].link].inv_link.push_back(v);

// 输出所有出现位置
void output_all_occurrences(int v, int P_length) {
  if (!st[v].is_clone) cout << st[v].first_pos - P_length + 1 << endl;
  for (int u : st[v].inv_link) output_all_occurrences(u, P_length);
}

我们在字符串 $S$ 的后缀自动机上做动态规划。

假定我们已经处理完了子串的一部分，当前在状态 $v$，想找到不连续的转移需要添加的最小字符数量，将节点 $v$ 处的这个数量记作 $d_v$。

计算 $d_v$ 非常简单。如果不存在使用字符集中至少一个字符的转移，则 $d_v=1$。否则添加一个字符是不够的，我们需要求出所有转移中的最小值：

$$d_v=1+\underset{w:(v,w,c)\in SAM}{min}{d}_w$$

问题的答案就是 $d_{t_0}$，字符串可以通过计算过的数组 $d$ 逆推回去。

我们对字符串 $S$ 构造后缀自动机。

我们现在处理字符串 $T$，对于每一个前缀，都在 $S$ 中寻找这个前缀的最长后缀。换句话说，对于每个字符串 $T$ 中的位置，我们想要找到这个位置结束的 $S$ 和 $T$ 的最长公共子串的长度。

为了达到这一目的，我们使用两个变量，当前状态 $v$ 和 当前长度 $l$。这两个变量描述当前匹配的部分：它的长度和它们对应的状态。

一开始 $v=t_0$ 且 $l=0$，即，匹配为空串。

现在我们来描述如何添加一个字符 $T_i$ 并为其重新计算答案：

• 如果存在一个从 $v$ 到字符 $T_i$ 的转移，我们只需要转移并让 $l$ 自增一。

• 如果不存在这样的转移，我们需要缩短当前匹配的部分，这意味着我们需要按照后缀链接进行转移：

  $$v=\mathrm{link}(v)$$

  与此同时，需要缩短当前长度。显然我们需要将 $l$ 赋值为 $\mathrm{len}(v)$，因为经过这个后缀链接后我们到达的状态所对应的最长字符串是一个子串。

• 如果仍然没有使用这一字符的转移，我们继续重复经过后缀链接并减小 $l$，直到我们找到一个转移或到达虚拟状态 $-1$（这意味着字符 $T_i$ 根本没有在 $S$ 中出现过，所以我们设置 $v=l=0$）。

显然问题的答案就是所有 $l$ 的最大值。

这一部分的时间复杂度为 $O(\left|T\right|)$，因为每次移动我们要么可以使 $l$ 增加一，要么可以在后缀链接间移动几次，每次都减小 $l$ 的值。

代码实现：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

string lcs(const string &S, const string &T) {
  sam_init();
  for (int i = 0; i < S.size(); i++) sam_extend(S[i]);

  int v = 0, l = 0, best = 0, bestpos = 0;
  for (int i = 0; i < T.size(); i++) {
    while (v && !st[v].next.count(T[i])) {
      v = st[v].link;
      l = st[v].length;
    }
    if (st[v].next.count(T[i])) {
      v = st[v].next[T[i]];
      l++;
    }
    if (l > best) {
      best = l;
      bestpos = i;
    }
  }
  return T.substr(bestpos - best + 1, best);
}

我们将所有的子串连接成一个较长的字符串 $T$，以特殊字符 $D_i$ 分开每个字符串（一个字符对应一个字符串）：

$$T=S_1+D_1+S_2+D_2+\cdots +S_k+D_k.$$

然后对字符串 $T$ 构造后缀自动机。

现在我们需要在自动机中找到存在于所有字符串 $S_i$ 中的一个字符串，为此可以利用添加的特殊字符。如果 $S_j$ 包含了一个子串 $X$，则从子串 $X$ 对应的节点 $t$ 出发，必然存在一条到达 $D_j$ 但是不经过任何其它特殊字符 $D_1,\cdots ,D_{j-1},D_{j+1},\cdots ,D_k$ 的路径。对于公共子串 $X$，应当对每个特殊字符 $D_j$ 都存在这样的路径。

因此我们需要计算可达性，即对于自动机中的每个状态和每个字符 $D_i$，是否存在这样的一条路径。这可以容易地通过 DFS 或 BFS 及动态规划计算。这之后，问题的答案就是所有能够达到所有特殊字符的状态 $v$ 对应的最长子串 $\mathrm{longest}(v)$ 中最长的那个。

不妨设 最短 的字符串为 $S_1$，对它构造 SAM。利用解决两个字符串最长公共子串的算法，计算剩余的每个字符串与 $S_1$ 的最长公共子串长度。在匹配过程中，每添加一个要匹配的字符串 $S_j$ 中的字符，就相应地在 SAM 上移动，因此，可以直接记录 在匹配过程中 SAM 每个状态能够匹配上的 $S_j$ 的最长子串的长度。

因为匹配过程中，每次匹配到 SAM 的一个状态时，必然同时匹配到了它在后缀链接树上的所有祖先节点，但是祖先节点的匹配长度的信息并没有更新。所以，在完成对字符串 $S_j$ 的匹配后，需要自下而上地沿着后缀链接更新，将子节点匹配到的最长子串的信息更新到父节点。此时，需要注意父节点记录的最长匹配长度不能超过它自身的 $\mathrm{len}$ 值。这样，就得到了 $S_1$ 的 SAM 上每个状态 实际能够匹配到 的 $S_j$ 的最长字串长度。

最后，只需要对每个 $S_2,\cdots ,S_k$ 都匹配一遍，再对 SAM 上每个状态记录的实际匹配到的长度取最小值，就得到 SAM 上每个状态实际能够匹配到的 $S_2,\cdots ,S_k$ 的最长公共子串的长度。然后，遍历 SAM 所有状态，取最大值就是这 $k$ 个串的最长公共子串长度。

算法时间复杂度是 $O(\sum _i|S_i|)$ 的。字符串 $S_1$ 的 SAM 虽然遍历了 $k$ 遍，但是因为 $|S_1|$ 是最小的，所以 $k|S_1|\le \sum _i|S_i|$，复杂度的主要项依然是匹配过程遍历所有子串。