SAM

notes

概述

增量法构造。

1
2
3
4
5
6
7
8
9
10
struct TREE{ int ne[SZ],fa,len,siz; }t[N<<1]; int las=1,tot=1;
void ins(int c){
    int p=las,np=++tot,v,nv; las=np,t[np].len=t[p].len+1;
    for(;p&&!t[p].ne[c];p=t[p].fa) t[p].ne[c]=np;
    if(!p) return t[np].fa=1,void(); v=t[p].ne[c];
    if(t[v].len==t[p].len+1) return t[np].fa=v,void();
    t[nv=++tot]=t[v],t[nv].len=t[p].len+1;
    for(;p&&t[p].ne[c]==v;p=t[p].fa) t[p].ne[c]=nv;
    t[v].fa=t[np].fa=nv;
}

普通后缀自动机

1.【模板】后缀自动机（SAM）

后缀自动机节点的 endpos 集合大小即为当前节点字符串的出现次数。

2.不同子串个数

  • 法一 DAG 上 DP

    性质：任意两个节点的表示集合没有交。

    记 $f_u$ 为从 $u$ 出发的路径条数即可。

  • 法二 统计树上每个节点的字符串个数即可。

3.[SDOI2016] 生成魔咒 - 洛谷

4.[TJOI2015] 弦论 - 洛谷

后缀自动机和 AC 自动机

parent 树可以看成对所有子串建立 AC 自动机。

1.LCS - Longest Common Substring

2.Cyclical Quest

3.[BJOI2020] 封印

后缀自动机和后缀树

反串的 parent 树就是后缀树。

1.[AHOI2013] 差异

2.[十二省联考 2019] 字符串问题

广义后缀自动机

就是后缀自动机插入多个字符串。

插入一个字符串后将 lst 设为 $1$，是常见的伪广义后缀自动机写法，但是时间复杂度是正确的。

1.[SNOI2020] 字符串

参考

常见字符串算法 II：自动机相关

后缀自动机学习笔记(应用篇)