如何手搓一个 SAM

注意！该博客只讲做法！

据某位高人所言，这位高人手搓 SAM 手搓了一个月，最终熟练使用了 SAM，得道后飞升为字符串之仙。

先看代码：

char s[N];
int tr[N][26], fail[N], len[N];
int np=1, tot=1, n;
void insert(int alp){
    int p = np;
    np = ++tot;
    len[np] = len[p] + 1;
    for(; p&&!tr[p][alp]; p=fail[p]) tr[p][alp] = np;
    if(p == 0) fail[np] = 1;
    else{
        int q = tr[p][alp];
        if(len[q] == len[p] + 1) fail[np] = q;
        else{
            int nq = ++tot;
            len[nq] = len[p] + 1;
            fail[nq] = fail[q], fail[q] = nq, fail[np] = nq;
            for(; p&&tr[p][alp] == q; p=fail[p]) tr[p][alp] = nq;
            memcpy(tr[nq], tr[q], sizeof tr[q]);
        }
    }
}

那么讲步骤：

1. SAM 包含一个 DAG 和一棵 Fail 树。每一个节点维护其在 DAG 上的出边、 和 。 为 代表的节点， 为新节点，即 代表的节点。 为存在 的第一个节点的 ，这个点本来是预定成为 的 。 为当 成为不了 的 时，拆出来的一个点，这个点才能成为 的 。
2. 新建节点 ，定其 为上一个节点 的 。
3. 将 沿着 Fail 树跳，将所有没有 的点的 设为 。直到跳出根或是 存在就停止。
4. 若 跳出根了，即 ，则设 。退出。
5. 否则，存在 。令其为 。
6. 若 ，则设 。退出。
7. 否则克隆节点。新建节点 ，定其 。
8. 然后将 的 转移至 ，再定 ，。
9. 然后再跳 ，将 设为 ，直到 跳出根或是 就停止。
10. 最后复制 的 DAG 出边信息至 。退出。

下面举几个例子（Fail 边用蓝色表示， 在右下角标注）：

い・ababc. 情况 1、2

建出 的 DAG 边。

建出 。

现在 成为了 ， 成为了 。然后 跳 Fail 树建边。

遇到没有 的全加上 边。

然后因为最后跳出了根，所以 。

现在 成为了 ， 成为了 。然后依然跳树建边。

但是注意！这里因为 是存在的，所以要进行处理。

定 ，即点 。然后因为 ，所以直接 ，结束。

首先还是跳树建边，直到发现存在 时，。

然后看 指向的是 。因为 ，所以建 。

这里 ，然后跳 ：因为不存在 ，所以建边 ，跳树；因为不存在 ，所以建边 ，跳树；因为不存在 ，所以建边 ，跳树；跳出根外，结束。赋 。这个字符串的 SAM 就建好了。

ろ・aabab. 情况 3

首先还是，插入 aa。

然后插入 b，跳树建边，最后连 fail。

然后插入 a，因为存在 ，并且 。所以设 为 即 。

现在插入 b，然后存在 。设其为 。但是现在 。那是否可以直接建 Fail 边呢？

答案是否定的。我们应该拆 点至 ，然后将 Fail 连向 。

那么首先，新建一个节点 ，然后设其 为 。

然后，修改 这三个点的 Fail：

• fail[nq] = fail[q]，将 的 修改为 ，即 。
• fail[q] = nq，将 的 修改为 ，即 。
• fail[np] = nq，将 的 修改为 。

然后，跳 来修改 ：

1. ，那么修改 ，跳链修改 。
2. ，那么修改 ，跳链修改 。
3. 跳出根外，结束。

注意一点：若 也要结束！

最后，复制所有 的出边至 ，拆点过程完成！

一个 aabab 的 SAM 就建好了！