SAM

401rk8 · 2021-12-16 17:39:06 · 个人记录

简单记录 SAM 的性质和例题用作复习和记忆，会持续更新，所以风格可能有一定区别

• oi-wiki
• 史上最通俗的后缀自动机详解
• 后缀自动机学习笔记(干货篇)，后缀自动机学习笔记(应用篇)

构建

建议先理解 ACAM

结论

• SAM 是接受一个字符串后缀的最小 DFA，最多有 2n-1 个结点和 3n-4 条边
• 子串 x,y（默认 |x|<|y|）的 \text{endpos} 相同等价于 x 在 s 每次出现都是以 y 后缀的形式
• 若 x 是 y 的后缀，则 \text{endpos}(y)\subseteq\text{endpos}(x)；否则 \text{endpos}(x)\cap\text{endpos}(y)=\varnothing
• 一个 \text{endpos} 等价类中子串长度连续，且较短者是较长者的后缀
• 通过 \text{endpos} 构造的树与后缀链接构造的树结点相同

手模

visualizer

由于 SAM 高度抽象，手模并不能帮助理解其性质。但一定要会手模，对背板&调试都有帮助。aabab 是一个很好的串

模板

代码很短且基本不会改动，建议全文背诵。注意 2 倍空间常数

struct SAM {
    int ind=1,lst=1,t[N][26],fa[N],len[N];
    void extend(int x) { // 加入字符 x
        int p = lst, np = lst = ++ind; len[np] = len[p]+1;
        // p: 原来的终止结点 np: 未来的
        for(; p && !t[p][x]; p = fa[p]) t[p][x] = np; // 加入未出现的新后缀
        if( !p ) fa[np] = 1; // 一直未出现
        else {
            int q = t[p][x]; // 在结点 q 出现了
            if( len[q] == len[p]+1 ) fa[np] = q; // q 没有比新后缀更长的串
            else { // 分裂：nq 表示新后缀及更短的，q 表示更长的
                int nq = ++ind; len[nq] = len[p]+1;
                memcpy(t[nq],t[q],sizeof(t[nq]));
                fa[nq] = fa[q], fa[q] = fa[np] = nq;
                for(; p && t[p][x] == q; p = fa[p]) t[p][x] = nq;  // 用 nq 代替 q
            }
        }
    }
} sam;

性质

• 任意两点表示的子串集合没有交
• parent 树上 fa[u] 代表的子串均为 u 代表子串的后缀
• u$ 代表的子串长度连续，为 $[\text{minlen}(u),\text{len}(u)]$，且 ${\rm minlen}(u)={\rm len}(fa[u])+1
• 原串 parent 树 = 反串后缀树
• 前缀 i,j 的 LCS = parent 树上 LCA 的 len

应用

P3804 【模板】后缀自动机 (SAM)

一个串的出现次数为所属 \text{endpos} 集合大小，即 parent tree 上子树和（构建时 np 的 \text{endpos} 集合大小为 1）

建树常数较大，可以通过基数排序实现

For(i,1,ind) ++buc[len[i]];
For(i,1,n) buc[i] += buc[i-1];
rFor(i,ind,1) id[buc[len[i]]--] = i;
rFor(i,ind,2) siz[fa[id[i]]] += siz[id[i]];

P2408 不同子串个数

• DAG

DAG 上一条路径对应一个子串。
设 f[u] 为从结点 u 出发的路径数，f[u]=1+\sum f[t[u,i]]，答案为 f[1]-1（不算空串）

• parent tree

每个结点代表一个 \text{endpos}，属于这个 \text{endpos} 的子串数量为 len(u)-len(fa[u])

SP1811 LCS - Longest Common Substring

类比 ACAM

对第一个串建 SAM，用第二个串在上面跑。记 l 为以当前位置结尾的匹配长度，若当前结点有需要的出边则 l+1，否则不断跳 fa 至有该出边，l 变为该结点的 len+1

P3975 [TJOI2015]弦论

求字典序第 k 大子串

用上一题的方法求出从每个结点出发的路径数，查询时类似主席树

// cnt[u]: 当前子串的贡献次数 sum[u]: 从 u 出发的路径数
void print(int u,int k) {
    if( k <= cnt[u] ) return;
    k -= cnt[u];
    Rep(i,0,26)
        if( k > sum[t[u][i]] ) k -= sum[t[u][i]];
        else return putchar('a'+i), print(t[u][i],k);
}

CF235C Cyclical Quest

不难想到破环成链在 SAM 上跑，但有两个问题：

1. 可能出现匹配长度大于原串长的情况。其实是需要删除首字符，记录匹配长度，若等于原串长则减一，若小于等于 len(fa) 则跳父亲
2. SAM 的一个子串可能和多个旋转匹配。在 SAM 结点上打标记或求原串的周期均可

P6640 [BJOI2020] 封印

对 t 建 SAM，然后用 s 在上面跑，求出 s 的每个前缀与 t 的最长公共子串长，记为 f[i]。那么答案为 \max_{i=l}^{r}\{\min(i-l+1,f[i])\}

发现与 i-l+1 取 \min 很难处理，考虑二分答案，合法条件为 \max_{i=l+mid-1}^{r}\{f[i]\}\ge mid，ST 表即可

彩蛋

学习 SAM 的正确姿势：

SAM模板的学习原则 : 理解性默写。—— command_block

感觉SAM性质比较少，背过就可以 —— yspm