广义后缀自动机（广义SAM）

· · 个人记录

参考博客：【学习笔记】字符串—广义后缀自动机

基础部分：后缀自动机(SAM)

广义后缀自动机适用于多串的子串问题。它的DFA可以识别多串中的任意一个子串。同时也有类似 SAM 的一些性质。

知识精要

广义SAM 的建立

模板提交处

根据参考博客所说，有好几种 假 写法。比如：每一个串的开头设置 lst 为 1；多串拼成一个大串，中间用'#'连接 等等；

正规写法：

离线做法

例题：P3346 [ZJOI2015]诸神眷顾的幻想乡

建出所有串的 Trie 树。然后在 Trie 上 bfs ，每次将一个字符加到其 Trie 的 fa 上。其余与 SAM 同。

$pos[cur]:Trie$ 上的 $cur$ 节点（所代表子串)在 SAM 上的位置 $int ins(int c, int lst):$ 几与普通SAM同。传入 $lst$，传出 $np Code: 
inline void work() {
    for (register int c = 0; c < 26; ++c)
        if (trie[1][c]) que[++rear] = trie[1][c];
    pos[1] = 1;
    while (front < rear) {
        int cur = que[++front];
        pos[cur] = ins(t_c[cur], pos[t_fa[cur]]);
        for (register int c = 0; c < 26; ++c)
            if (trie[cur][c])   que[++rear] = trie[cur][c];
    }
}

在线做法

每一个串的开头设置 lst 为 1。但是由于一开始可能就存在 son[lst][c]，那就不太妙。因此需要加两个特判：

特判一

if (son[lst][c] && len[son[lst][c]] == len[lst] + 1)    return son[lst][c];

如果有一个完美的节点 q，那么我们直接将 lst 设置为这个点返回即可。

特判二

//...
//if (len[q] == len[p] + 1) return ...
if (p == lst)   flag = true;
//int nq = ++tot; len[nq]...

如果存在一个不那么完美的节点 q，那么我们可以新建一个节点 nq，然后...（同SAM）。这样我们就和普通 SAM 合并一下，在最后判断一下，如果是这种情况，就直接返回 nq 即可。可以证明的是，此时建立的 p 节点是一个“空点”，因为 len[p] = len[lst] + 1, minlen[p] = len[nq] + 1 = len[lst] + 2。

代码

inline int ins(int c, int lst) {
    if (son[lst][c] && len[son[lst][c]] == len[lst] + 1)    return son[lst][c];
    int np = ++tot, p = lst;
    len[np] = len[p] + 1;
    while (p && !son[p][c]) son[p][c] = np, p = fa[p];
    if (!p) return fa[np] = 1, np;
    int q = son[p][c];
    if (len[q] == len[p] + 1)   return fa[np] = q, np;
    bool flag = false;
    if (p == lst)   flag = true;
    int nq = ++tot; len[nq] = len[p] + 1;
    fa[nq] = fa[q], fa[q] = fa[np] = nq;
    memcpy(son[nq], son[q], sizeof(son[q]));
    while (p && son[p][c] == q) son[p][c] = nq, p = fa[p];  
    return flag ? nq : np;
}

在线做法由于空间开得小，码量也小，一般使用在线做法，但是离线做法的思想也要知道。

在建立广义SAM的同时，还可以维护每个串的 endpos 集合，应用 len 的性质等等。具体见下方。

技能展示

识别某串是否是多串中某串的子串

直接建广义SAM，在DFA上跑即可。

多串中本质不同子串个数

建广义SAM，ans = \sum{len[i] - len[fa[i]]}

维护每个串的 endpos 集合

在加入(ins)时，对于表示当前串的节点 的siz 赋值为 1。（注意特判的地方，如果找到了个“完美的替身”，那么让替身的 siz 为1；如果确实要让nq代替np，那么将np的siz的那个1转移给nq）然后再按照类似普通SAM的做法搞出 endpos 集合。（搞firstpos后线段树合并）

求多串最长公共子串

SP1812 LCS2 - Longest Common Substring II

建立多串的广义SAM，同时维护每个串的 endpos 集合（大小）。最后检查每个节点是否“被所有节点共同拥有”。如果有这样的节点，那么可以用这个节点的 len 更新答案。

例题

#3473. 字符串

调到心态爆炸，暂时放弃。

记录在这里：my record

附

模板（调试用）

inline int ins(int c, int lst) {
    if (son[lst][c] && len[son[lst][c]] == len[lst] + 1)    return son[lst][c];
    int np = ++tot, p = lst;
    len[np] = len[p] + 1;
    while (p && !son[p][c]) son[p][c] = np, p = fa[p];
    if (!p) return fa[np] = 1, np;
    int q = son[p][c];
    if (len[q] == len[p] + 1)   return fa[np] = q, np;
    bool flag = false;
    if (p == lst)   flag = true;
    int nq = ++tot; len[nq] = len[p] + 1;
    fa[nq] = fa[q], fa[q] = fa[np] = nq;
    memcpy(son[nq], son[q], sizeof(son[q]));
    while (p && son[p][c] == q) son[p][c] = nq, p = fa[p];  
    return flag ? nq : np;
}

Continued...