[学习笔记] 后缀自动机

2024-02-25 09:04:04

其实我后缀自动机在 \(2020/2\) 的时候就会了，刷了很多题，但是一直没有搞懂原理，现在补一发关于后缀自动机原理的博客。我尽量节约时间，把最重要的东西写的尽量好理解。

我是看这位巨佬的博客学的，所以会有一些重合的地方，但是我会按照我自己的理解写（仔细看你会发现我们的表述相差很大），争取达到一个优化的效果。

什么是后缀自动机？

这才是究极大暴力，学会了之后随便切很多字符串毒瘤题。

他主要干的事情是维护一个字符串中的所有子串，但是基础复杂度却能保证是 \(O(n)\) ，此外还有很多优美的性质 \(....\) 原谅我现在没有办法一一向你介绍，具体可以看最后的部分 后缀自动机应用

中心思想是 \(\tt endpos\) ，也就是维护子串的 出现结束位置集合 。

一些基础的结论

\(\tt endpos\) 有很多优美的性质，且看我一一向你介绍。

结论1：\(\tt endpos\) 相同的两个字符串 \(A,B\;(|A|\leq |B|)\) ，满足 \(A\) 一定是 \(B\) 的后缀。

~~这么明显的结论为什么不感性理解呢？~~

证明的话考虑他们 \(\tt endpos\) 完全相同，那么 \(B\) 出现的话一定会连带着 \(A\) 出现。对于每个结束位置都如此，不难发现 \(A\) 是 \(B\) 的后缀。

现在你应该能感知到为什么要叫后缀自动机，因为 \(\tt endpos\) 会连带着一些关于后缀的性质。

结论2：对于两个字符串 \(A,B\;(|A|\leq |B|)\) ，那么要么 \(\tt endpos(B)\subseteq endpos(A)\) ，要么 \(\tt endpos(A)\cap endpos(B)=\empty\)

~~其实也很好感性理解呀！~~

我们就要证明不会出现相交的情况，使用反证法，假设出现了相交。那么 \(B\) 出现的某些地方会出现 \(A\) ，\(B\) 出现的另一些地方又不会出现 \(A\) ，显然矛盾，所以只会有包含或者是不交的情况。

结论3：对于 \(\tt endpos\) 相同的子串，我们将其归为一个 \(\tt endpos\) 等价类，对于每一个等价类按长度排序，每一个子串的长度都等于上一个字串的长度\(+1\)

~~好显然啊！~~

我们假设这个等价类中最长的子串是 \(len\) ，那么最短的子串是 \(jzm\) ，显然 \(jzm\) 是 \(len\) 的一个后缀。那么既然 \(jzm\) 都可以被划分到这个等价类中，所以长度在他们中间的一定都会划分到这个等价类中。

有了这个结论，我们可以用 \(len(i)\) 表示第 \(i\) 个 \(\tt endpos\) 等价类的很多信息了，也就是我们只需要维护等价类中最长的子串。

结论4：\(\tt endpos\) 等价类的个数为 \(O(n)\)

这个结论是后缀自动机复杂度得到保证的关键，~~我不敢再说显然了~~

我们考虑用树形关系来表示 \(\tt endpos\) 之间的联系，如果 \(i\) 等价类是 \(j\) 等价类的父亲，那么 \(i\) 等价类的所有子串都是 \(j\) 等价类所有子串的后缀。而因为结论 \(2\)，我们知道 \(i\) 的所有儿子 \(j\) 所表示的 \(\tt endpos\) 集合一定是不交的。

这样可以用一种划分关系来理解这个树形结构，也就是我们会把 \(i\) 的 \(\tt endpos\) 划分分给他的儿子。一共只会划分 \(n-1\) 次就可以到达底层，而 \(1\) 个点的作用相当于划分了一次，所以点数 \(O(n)\)

我们把这样的树形关系叫做 \(\tt parent\;tree\) ，这棵树就是后缀自动机的关键。

如何构建后缀自动机

上面的结论主要是说明了后缀自动机的可行性和一些关键特征，现在我们来解决具体的构建。

后缀自动机之所以叫自动机，是因为他也有所谓的 转移 ，就像 \(\tt AC\) 自动机一样。

后缀自动机的转移是这个意思：在这个点的子串后面加上一个字符 \(c\) 所能到达的点（子串的长度要尽量短）。如果我们能构造出转移，那么这个自动机就很好用了。现在我们先来看代码吧，我会逐一讲解代码：

void add(int c)
{
    int p=last,np=last=++cnt;val[cnt]=1;
    a[np].len=a[p].len+1;
    for(;p && !a[p].ch[c];p=a[p].fa) a[p].ch[c]=np;
    if(!p) a[np].fa=1;
    else
    {
        int q=a[p].ch[c];
        if(a[q].len==a[p].len+1) a[np].fa=q;
        else
        {
            int nq=++cnt;
            a[nq]=a[q];a[nq].len=a[p].len+1;
            a[q].fa=a[np].fa=nq;
            for(;p && a[p].ch[c]==q;p=a[p].fa) a[p].ch[c]=nq;
        }
    }
}

我们一个一个加入字符，所以我们处理的是原串前缀的后缀自动机。但是现在我们叫加入 \(c\) 之前的字符串为原串，加入 \(c\) 之后的串为新串，那么 \(np\) 其实是整个新串对应的节点，要干的事有两个：把 \(np\) 连进图中 \(/\) 原串后缀加上 \(c\) 之后的 \(\tt endpos\) 可能变化，所以这也要修改一下。

int p=last,np=last=++cnt;val[cnt]=1;
a[np].len=a[p].len+1;

这两句话就是基本的定义，很显然，没有什么要讲的。

for(;p && !a[p].ch[c];p=a[p].fa) a[p].ch[c]=np;
if(!p) a[np].fa=1;

这一部分就是修改 \(p\) 和他的祖先关于 \(c\) 的转移，如果他们没有东西可以转移，那么转移到 \(np\) 就是极好的（其实结合转移的定义就不难理解了），下一句话是如果 \(1\)（根）都没有 \(c\) 可以转移，那么显然 \(c\) 是在原串中没有出现过的，所以 \(np\) 直接成为 \(1\) 的儿子。

int q=a[p].ch[c];
if(a[q].len==a[p].len+1) a[np].fa=q;

现在的 \(p\) 已经是第一个有转移的祖先了，我们先拿到 \(p\) 的转移 \(q\)，那么如果 \(len[q]=len[p]+1\) ，那么说明 \(q\) 一定是 \(p\) 的最长子串后面再接上一个 \(c\) 的结果，这简直就是无缝连接啊！然后不难看出 \(q\) 一定是 \(np\) 的后缀，所以把 \(np\) 的父亲设置为 \(q\) 是 \(\tt make\; sense\) 的。

int nq=++cnt;
a[nq]=a[q];a[nq].len=a[p].len+1;
a[q].fa=a[np].fa=nq;
for(;p && a[p].ch[c]==q;p=a[p].fa) a[p].ch[c]=nq;

这种情况就是 \(len[q]>len[p]+1\) ，也就是 \(q\) 是 \(p\) 的最长子串后面再加上若干字符。这种情况不能直接设置父亲，因为加上若干字符之后就不满足了后缀关系。那么我们考虑建一个新点 \(nq\) ，那么 \(len[nq]=len[p]+1\)，也就是它代表了 \(p\) 代表的字符串直接接上 \(c\) 字符的结果。\(nq\) 相当于把一个子串拆出来。

那么现在就满足后缀关系了，\(q\) 和 \(np\) 的父亲都可以直接赋值为 \(nq\)

现在也不要忘了更新转移哟，对于 \(p\) 以及 \(p\) 的祖先中转移是到 \(p\) 点的话，现在转移就要改成 \(nq\) 点了。结合转移的定义就知道我们要找的是长度最小的点，所以肯定转移到 \(nq\) 啊。

现在进入喜闻乐见的复杂度证明环节：由于边数和点数都是 \(O(n)\) 的，观察所有的操作发现时间复杂度 \(O(n)\)

后缀自动机的应用

会慢慢补充的 \(....\)

码农公寓