后缀自动机-SAM

zuytong · 2022-10-09 09:01:06 · 个人记录

link to cnblog

基础模型

初学 SAM，感觉这东西实在是抽象...

建议就是感性理解 + 背板子

参考资料：

OI-Wiki

cmd 的博客

\text{endpos}

首先我们来了解什么是 \text{endpos} ：

而 $\text{endpos}(t)$ 表示为：$s$ 中**所有**的子串 $t$ 的结束位置形成的集合例如：`ababc`，$\text{endpos}($`ab`$)=2,4$；$\text{endpos}($`abc`$)=5

- 1. 对于两个本质不同子串的 $\text{endpos}$ : $a,~b$，要么是 $a \subseteq b$ 或 $b \subseteq a$，要么是 $a \cap b = \oslash

换句话而言，就是两个 \text{endpos} 要么是包含关系，要么是相离，不可能出现交叉

1. 若 q 为 p 的后缀，那么有 \text{endpos}(p)\subseteq \text{endpos}(q)
1. 对于一个等价类（就是同一种 \text{endpos} 的所有子串），将字符串按长度从小到大排序后，前一个字符串始终为后一个字符串的后缀，且长度是连续的

parent tree

上面 \text{endpos} 的引理，都在说明我们可以建立一棵树

对于一个等价类，设它最长的字符串为 smax，我们在 smax 前加入若干字母，那么显然这个新串不属于这个等价类

但显然，新串对应的等价类是原串等价类的子集

因此我们可以利用这个子集关系建立一棵树，称为 parent tree

其实这可以看成将一个等价类分裂成若干个类，然后成为原等价类的儿子

parent tree 中，由儿子指向父亲的链成为后缀链接

那它与 SAM 有什么关系呢？

其实，SAM 上的结点意义与 parent tree 的意义相同

而且可以证明，依靠 parent tree 建立出来的 SAM，结点数（自动机状态）不超 2n-1，边数（自动机转移）不超 3n-4，让 SAM 做到线性级别

下面是 SAM （左）与 parent tree （右）的对比（原串："abcbc"）

（其中绿色结点表示终止链上的结点）

构建 SAM

先放代码，逐层分析：

struct Node
{
    int nxt[26], lk, len;
}a[N << 1 | 5];
int tot, la;
inline void sam_expand(int c)
{
    int now = ++tot, p = la;
    a[now].len = a[p].len + 1;
    for(; ~p && !a[p].nxt[c]; p = a[p].lk) a[p].nxt[c] = tot;
    if(p == -1) a[now].lk = 0; // case 1
    else
    {
        int q = a[p].nxt[c];
        if(a[p].len + 1 == a[q].len) a[now].lk = q; // case 2
        else
        {
            int nq = ++tot;
            a[nq] = a[q], a[nq].len = a[p].len + 1;
            for(; ~p && a[p].nxt[c] == q; p = a[p].lk) a[p].nxt[c] = nq;
            a[now].lk = a[q].lk = nq;
        } // case 3
    }
    la = now;
}

变量解析：

struct Node
{
    int nxt[26], lk, len;
}a[N << 1 | 5];
int tot, la;

nxt[] 表示自动机的转移，lk 表示后缀链接，len 表示这个等价类最长的字符串的长度

tot 表示结点（状态）个数，la 表示终止链的位置

最开始我们要初始化空的根节点 0：

a[0].lk = -1

现在每次在串最后增加一个字符：

int now = ++tot, p = la;
a[now].len = a[p].len + 1;

新建一个结点

for(; ~p && !a[p].nxt[c]; p = a[p].lk) a[p].nxt[c] = tot;
if(p == -1) a[now].lk = 0; // case 1

我们将终止链上状态都转移到现在的状态，这样就加入了新的后缀

如果 p=-1，代表新后缀在之前都没出现过，也就不是任何等价类的子集，因此后缀链接指向根节点

else
{
    int q = a[p].nxt[c];
    if(a[p].len + 1 == a[q].len) a[now].lk = q; // case 2
    else
    {
        int nq = ++tot;
        a[nq] = a[q], a[nq].len = a[p].len + 1;
        for(; ~p && a[p].nxt[c] == q; p = a[p].lk) a[p].nxt[c] = nq;
        a[now].lk = a[q].lk = nq;
    } // case 3
}

否则，代表之前的串就已经出现了新后缀的状态，我们要分两种情况讨论（q 就是出现过的新后缀的状态位置）：

q 的等价类只有一个串：那么这个串就是新后缀，因此直接将等价类扩展即可，将后缀链接指向 q
否则，q 的等价类大小应该小于新后缀对应的等价类，因此我们要将它替换掉：

我们新建一个状态 nq，将 q 中除了 len 复制到 nq 中，而 nq.len=p.len+1
接着，继续遍历终止链，将原来指向 q 的状态，改为指向 nq
最后，将 q 和新后缀的等价类的后缀链接指向 nq

这样能保持 SAM 与 parent tree 的性质

模板题

显然，每个串的 \text{endpos} 的元素个数，就是出现的次数

我们可以在 parent tree 上跑树形 dp，计算 u 子树内 sz 和，当 sz_u > 1 时，计算 a[u].len\times sz_u，与答案取最大值

注意 sz 的初始化：应为每次加入一个字符时，将新状态的 sz=1

代码