再学串串（四）：后缀是后缀的后缀是后缀的后缀

· · 算法·理论

花了近一周憋了个大的，发现错误或者有建议私信评论反馈都可以，会尽快响应。

过去的章节

  1. 再学串串（一）：我真的学会 KMP 了吗？评「clx201022 式的傲慢」
  2. 再学串串（二）：AC 自动机不是自动 AC 机
  3. 再学串串（三）：被构造自动机上计数 DP 题吓晕

目前已同步在博客园更新。

上文评论区中某人建议道：

该进军基本子串结构了

但我不会，所以接下来是 SAM（Suffix AutoMaton，后缀自动机）和 SA（Suffix Array，后缀数组）。

:::info[马拉车问了吗？]

马拉车速度没有万用自动机快，所以要再等一会。

:::

第四站：后缀自动机——不止后缀

一个后缀自动机（SAM）是接受特定字符串 T 所有后缀的 最小 自动机。

我想说的是，自动机是一个很广泛的概念，你不会的东西是构造一个能精准刻画题目条件的、状态数尽量少的、（有限状态）自动机，而不是不会字符串算法，换成别的条件例如子序列个数也能用有限状态自动机刻画

这句话很好地体现了后缀自动机的核心：最小。

字典树 Trie 在图论意义下是一棵树——其每个状态 x 经过任意字符串转移到的所有状态都不可能在非 x 子树的任何其他位置。这个性质使得字典树易于维护；但同时，这个性质也使得字典树在所有等价自动机^dengjia中往往不是最小的。

如果只需要能构造出即可，那么字典树就够用了。但由于是最小，才有了「后缀自动机」这个概念的出现。

后缀自动机虽然名字上带个「后缀」，但它首先是个「自动机」，这就注定了它是带有「前缀性」的。而前缀的后缀，就是任意子串了。所以，你也可以叫它「子串自动机」。

性质

只说「最小」有些笼统，也不利于系统地构造后缀自动机的概念，所以接下来尝试思考一个已经构造好的后缀自动机会有哪些性质。

如果没有具体的例子的话性质是较难找的，因此从别的地方借（偷）一个现成的后缀自动机进行研究。

对字符串 T = \texttt{qwqaqwq} 构造后缀自动机：

不同于字典树是树，KMP 自动机可能有环，后缀自动机是一个一般意义上的 DAG。

自动机上红框标注的为 接受状态。

起点开始的每条路径都与一个 T 的子串对应。将原自动机上所有 非失配状态 作为 接受状态，可得到一个匹配 T 所有子串的一个自动机。

:::info[证明]

设 T 长度为 n。

要证明的命题成立当且仅当以下两个命题成立：

  1. 起点开始的每条路径必然有一个 T 的子串相对应。
  2. 每一个 T 的子串必然有一条起点开始的路径相对应。

假设存在一个从起点开始的每个路径没有对应的 T 的子串。由于其不为 T 的子串，所以最后必然不能构造出 T 的后缀。根据后缀自动机的最小性，这样的路径必然可以省去。

假设存在一个 T 的子串 T[p,k] 没有对应的从起点开始的路径。考虑将找到一个包含该子串的 T 的后缀 T[k,n]，容易得出这是平凡的。该后缀的路径上必然是包含该子串的，这与假设矛盾，所以假设不成立。

Q.E.D.

:::

发现无论是 \texttt{a} 还是 \texttt{qa}，抑或着是 \texttt{wqa}，都对应着同一个状态 5。如何区分这三个子串？

答案很简单：不需要区分。

等价类

在样例 T 中，\texttt{a} 出现的位置，前面必然是 \texttt{wq}。我们并不关心在状态之前具体经过的前缀，而只关心目前的前缀路径对应的串 S 在 T 的哪些位置出现过。

令 endpos_S 是子串 S 到其可能在 T 出现的结束位置，称 endpos 相同的子串在一个等价类 E（虽然叫做类，但它实际上是一个字符串集合）内。

关于 endpos 和等价类，对于非空字符串 A,B，有以下引理：

  1. 如果 A 是 B 的后缀，那么 endpos_B \subseteq endpos_A。
  3. 设 |A|\le|B|，则 endpos_A\cap endpos_B=\varnothing 当且仅当 A 不是 B 的后缀。
  4. 一个非空等价类 E 内，必然存在一个最长串 B，其余所有 A\in E 都是 B 的后缀。
  5. 若 B 的后缀 B[l,|B|] 和 B[r,|B|] 同属于一个等价类 E，则 \forall l\le x\le r,B[x,|B|]\in E。

（具体证明可见这篇文章）

由上述引理可以得出，一个等价类应该是形如 \{S[l,m],S[l+1,m],S[l+2,m],\dots,S[r,m]\} 的，其中 S 为一个长 m 的 T 的前缀。

如果说 KMP 自动机中状态的含义是文本串 T 后缀 K 同时是 模式串 S 前缀的最长长度，那么后缀自动机状态的含义就是就是文本串 S 前缀最后一位可能在的所有位置 endpos_S，即除起点状态 t_0 作为起点外每个状态都对应一个等价类 E_{endpos_S}。（这里两个自动机模式串和文本串定义是反的，这是由于如果用后缀自动机进行字符串匹配，是对于被匹配的串 T 建后缀自动机）

由此，后缀自动机状态转移的思路也就明确了：根据目前的 endpos_S 和下一个字符 c，转移到 endpos_{S'}（S'=S+c）。

而对于一个状态 p，由起点状态可能转移其的所有路径对应的字符串组成的集合即为 p 所对应的等价类。如样例中，\{\texttt{w},\texttt{qw}\} 就是 S 结束位置在 T 第二个字符或第六个字符的一个等价类；而 \{\texttt{a},\texttt{qa},\texttt{wqa},\texttt{qwqa}\} 是 S 结束位置在 T 第四个字符的一个等价类。

如仅由 \texttt{q} 不能确定目前匹配在哪个位置，但若再往后加一个 \texttt{w} 或者 \texttt{a} 即可缩小范围。（如果都不是呢？那就进入 失配状态 了！）

其中「缩小范围」提醒我们：往后添加字符的过程，同时也是排除最终子串 S 在哪些地方「不可能出现」，也即通过「信息」减小「可能范围」的过程。

由此可以容易推出一个跟前后缀拼接有关的结论：

  1. 若 A+B=C，则有 endpos_C \subseteq \{x+|B|\}(x\in endpos_A)。

后缀链接

仿照 KMP 自动机的 next 数组，后缀自动机应也有一个类似的指针状物辅助进行状态转移，同时借助这个指针状物从前往后根据 T 的每个字符构造自动机。

任务就转化为了已对 T （|T|=n）构建好了一个后缀自动机，现在有 T'=T+c （|T'|=n'=n+1）要求在 T 后缀自动机的基础上增加一些状态或边以构造 T' 的后缀自动机。

因为每个点都对应一个等价类，所以点的变化即是等价类的变化，而等价类的变化即对应着 endpos 的变化，此处设 T' 的等价类使用的是 endpos'。

所有 $T'$ 的非空后缀 $S'$ 除 $c$ 外都对应一个 $T$ 的非空后缀 $S$。这些 $S$ 必然在若干个等价类内，而每个等价类对应一个状态。如何维护这些状态？ 实时维护 $T$ 在 $T$ 自身内对应等价类 $E_{endpos_T}$ 的状态，所有这些 $S$ 要么与 $T$ 在同一个等价类内，要么有 $|S|<\min_{K\in E_{endpos_T}}|K|$。 找到 $T$ 所有非空后缀中最长的不与 $T$ 在同一等价类的 $X$，连一条由 $E_{endpos_T}$ 对应状态到 $E_{endpos_X}$ 对应状态的边，再对于 $X$ 找到其所有非空后缀中最长的不与 $X$ 在同一等价类的 $Y$，重复此过程。 根据 **引理 $4$** 和 **引理 $5$**，可以推测出最后会得到一个类似 KMP 自动机 $fail$ 树的结构，从 $E_{endpos_T}$ 一直往上跳即可遍历 $T$ 所有非空后缀 $S$ 所在的等价类。仿照 KMP 自动机中的 $next$ 数组和 $fail$ 树，将其称为后缀链接 $link$ 和后缀链接树 $linktree$。[^linktree] 定义 $link(X)=Y$ 为满足尽可能长的不与 $X$ 在同一等价类的 $X$ 的后缀 $Y$；基于 $X$ 和 $Y$ 对应的状态也作类似的定义。 由以上定义，有引理： 7. $endpos_X\subsetneq endpos_Y
  1. 设 E_{endpos_X} 中存在最短串 Z，有 |Z|=|Y|+1。

即 X 出现过的位置 Y=link(X) 必然也出现过，并且 Y 必然还在一些 X 未出现过的位置出现过。

:::info[引理 8 证明]

对 Z 不可能有 |Z|<|Y|+1，否则根据 引理 5，Y 与 X 在一个等价类内，与 Y 定义矛盾。

对 Z 同样不可能有 |Z|>|Y|+1。|Z|>|Y|+1 时，必然存在串 A 使得 |Y|<|A|<|Z|，A 与 X 在一个等价类内与 Z 的定义矛盾，否则与 Y 的定义矛盾。

综上，|Z|=|Y|+1。

Q.E.D.

:::

在 引理 6 的基础上，考虑 B 为单个字符，思考等价类之间的关系，在自动机的状态转移上，有：

  1. 对于状态 p 和其通过 c 转移到的状态 q=\delta(p,c)，有 \forall P\in E_p[\exist Q\in E_q[Q=P+c]]，也即 E_q\supseteq \{P+c|P\in E_p\}，取等当且仅当不存在另一个 p'\ne p 也满足 q=\delta(p',c)。若存在 p'，则要么 p' 在 p 的后缀链接树到根的路径上，要么 p 在 p' 的后缀链接树到根的路径上；这等价于要么 E_p 所有元素全是 E_{p'} 的后缀，要么 E_{p'} 所有元素全是 E_{p} 的后缀。

证明可由读者根据等价类与状态转移之间的关系自行完成。

状态转移

类比于 KMP 的跳 next 前缀构造新的 next，SAM 是跳 link 后缀构造新的 link。

根据 引理 9，对于每个状态 p，所有到 p 的转移边上面的字符都与 p 等价类内所有字符串的最后一个字符 c 相同。这个推论在后面可能会用到。

思考 endpos\to endpos' 的变化导致的等价类的变化。

平凡地，每次必然新增一个等价类 E_{\{n'\}}={T'}，设其对应的状态为 cur。

如何处理 endpos'_{S'}= endpos_{S'}\cup \{n'\}？

设 S'=S+c，K'=K+c。

对于 K'\in E_{endpos_{S'}},|K'|<|S'|。K' 是 S' 的后缀，S' 是 T' 的后缀，K' 作为 T' 的后缀必然也有 endpos'_{K'}= endpos_{K'}\cup \{n'\}。

而对于 K'\in E_{endpos_{S'}},|K'|>|S'|，S' 为 K' 的后缀。此时不能保证 K' 为 T' 的一个后缀，原有的等价类可能需要分裂，情况开始变得复杂起来了。

显然 S 为 K 的一个后缀。因为 T'=T+c，所以 K' 不为 T' 的一个后缀当且仅当 K 不为 T 的一个后缀。因为 S 为 T 的一个后缀，所以 endpos_K\subsetneq endpos_S，即 S 与 K 不在一个等价类内。但我们限定了 S' 与 K' 在 endpos 内同一个等价类内。由此可以推出 c 在 T 中没有出现在任何不为 K 后缀形式的 S 的后面。形式化地，\nexists a[a\in enpos_S\land a\notin endpos_K\land T_{a+1}=c]。

构造

依照前文，从 E_{endpos_T} 对应状态 last 沿 link 上溯。设当前上溯到的状态 p 原对应等价类为 E_{endpos_P}，其中 P 在 E_{endpos_P} 中长度最长。

不断上溯并对未定义的 \delta(p,c) 赋值 cur，\delta(p,c) 未定义当且仅当其 endpos 中没有一个元素 a 满足 T_{a+1}=c，即不存在可能使原有等价类分裂的 S。

如果一直上溯到 t_0，则 T 的后缀自动机不存在 p 有 \delta(p,c) 定义时，即 E_{endpos_P} 内不存在任何一个子串后一个字符是 c 的情况。此时 T' 的所有后缀都在同一等价类内，将所有 \delta(p,c)\gets cur，同时 link(cur)\gets t_0 表示不存在非空的不在同一等价类内的后缀。

重复直到存在 q = \delta(p,c)，令 E_q 为状态 q 所对应的等价类。E_q 无需分裂当且仅当对于所有 Q\in E_q 都有 endpos'_{Q}= endpos_{Q}\cup \{n'\}，这等价于最长的 Q 满足 |Q|=|P|+1。此时 link(cur)\gets q 即可。

:::info[证明]

此时 E_q 对应 S' 和 K' 所在的等价类，E_p 对应 S 所在的等价类。要想使 E_q 不分裂，即要求对任意 K 都有 endpos_K=endpos_S。E_q 中最长串 Q，总有 |Q|\ge|P|+1，否则可以构造出一个更长的 Q'，与 Q 为最长串相矛盾。而若 |Q|>|P|+1，根据 引理 9，存在 P'\in E_{p'},q=\delta(p',c),p'\ne p，然后因为等价类和状态是一一对应的，所以 endpos_{p'}\ne endpos_p，把它们分别对应 K 和 S 就可以推出 E_q 必然分裂，从而证明必然有 |Q|=|P|+1 了。

Q.E.D.

:::

否则 E_q 将其中 Q\in E_q,|Q|>|P|+1 的部分分裂出状态 q' 作为一个新的等价类 E'_{q'} = \{Q'|Q'\in E_q,|Q'|>|P|+1\}。

剩下原来的状态内 Q\in E'_q 做一遍 endpos'_{Q}= endpos_{Q}\cup \{n'\}，体现到后缀链接上就是 link(cur)\gets q。

然后所有 \delta(p',c)=q 的所有 p' 必然都在 last 到 t_0 的路径上，将其中 last 到 p 路径（不包括 p）的 p' 全部重定向到 q'。根据 引理 8，对其中满足 link(p')=p 必然有 X\in E_{p'},|X|=|P|+1，其中 P 为 E_p 中最长的串。|X|+1>|P|+1，重定向到 q' 才能保证 引理 9。

由于 q' 的最长串长度是大于 q 的，所以 link(any)=q 应当重定向到 link'(any)=q'。但是一个个重定向时间复杂度会爆炸还很难维护。因此实际操作的时候是从 E_q 里面把 E'_q 分裂出去吧而将 E'_{q'} 留在原位，重定向 \delta(p',c) 则是将 p 到 t_0 重定向到 E'_q。

对于每个状态维护一下对应等价类的最长长度、后缀链接和转移边然后照上文步骤实现即可。

以 T=\texttt{qaqawawaqwq} 为例，其生成出来的自动机和后缀链接树就是这个样子的：

感兴趣的读者可以试着自己推一推。

程序实现

:::success[P3804 【模板】后缀自动机（SAM）]

每个等价类内考虑最长串即可，注意考虑后缀链接代表的等价类间的后缀包含关系。（与 AC 自动机匹配要考虑 fail 树代表的前缀包含关系同构）

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e6;
string S;
struct state
{
    int len, link;
    unordered_map<char, int> to;
    state(int len = 0, int link = 0, unordered_map<char, int> to = unordered_map<char, int>()) : len(len), link(link), to(to){}
};
state st[maxn << 1 | 1];
int st_cnt, lst;
vector<int> e[maxn << 1 | 1];
int siz[maxn << 1 | 1];
void sam_extend(char c)
{
    int cur = ++st_cnt;
    siz[cur] = 1;
    st[cur].len = st[lst].len + 1;
    int p = lst;
    while (p && !st[p].to.count(c))
    {
        st[p].to[c] = cur;
        p = st[p].link;
    }
    if (!p)
    {
        st[cur].link = 1;
    }
    else
    {
        int q = st[p].to[c];
        if (st[p].len + 1 == st[q].len)
        {
            st[cur].link = q;
        }
        else
        {
            int qci = ++st_cnt;
            st[qci] = st[q];
            swap(q, qci); // 因为 link。。。
            st[q].len = st[p].len + 1;
            // q 是原等价类里 |Q| <= |P| + 1 的(P 为 p 等价类内最长串)
            // qci 就是 |Q| > |P| + 1 的
            while (p && st[p].to[c] == qci)
            {
                st[p].to[c] = q;
                p = st[p].link;
            }
            st[qci].link = st[cur].link = q;
        }
    }
    lst = cur;
}
ll ans = 0;
void dfs(int u)
{
    for (auto v : e[u])
    {
        dfs(v);
        siz[u] += siz[v];
    }
    if (siz[u] != 1) ans = max(ans, 1ll * siz[u] * st[u].len);  // 出现次数不为 1
}
void get_SAM()
{
    st[lst = st_cnt = 1] = state();
    for (int i = 0; i < S.size(); i++) sam_extend(S[i]);
    for (int i = 2; i <= st_cnt; i++) e[st[i].link].emplace_back(i); /*
    for (int i = 1; i <= st_cnt; i++)
    {
        cout << i << ' ' << st[i].link << " link" << endl;
        for(char c = 'a'; c <= 'z'; c++)
        {
            if(st[i].to.count(c)) cout << i << ' ' << st[i].to[c] << string(" ") + c << endl;
        }
    }
    */
    dfs(1);
}
int main()
{
    cin >> S;
    get_SAM();
    cout << ans;
    return 0;
}

:::

由于篇幅已经较长且信息量极大，所以关于 SA 的内容只能且听下回分解了。

友链

警示后人

你知道吗不要在晚上睡觉前听求&影并且开单曲循环不然每次碰到 Q.E.D. 的时候都会忍不住唱出来。

创作声明

本文遵循 CC BY-NC-SA 4.0 协议。

保证本文未使用任何 AI 工具辅助创作。

转载例如下：

[原文](https://www.luogu.com.cn/article/b3zc5pv4)作者为 [clx201022](https://www.luogu.com.cn/user/552688)，转载人保证会遵循 [CC BY-NC-SA 4.0](https://creativecommons.org/licenses/by-nc-sa/4.0/deed.zh-hans) 协议：以适当的方式署名，不以盈利为目的进行转载，并以相同方式共享此文。

[^linktree]: 本文中提及的后缀链接树与这个 linktree 没有任何关系。