SAM 后缀自动机小结
后缀自动机
资料
笔记
后缀自动机上每个点代表的是一些 $endpos$ 相同且长度连续的一些字符串，状态 $u$ 表示的字符串的长度范围为 $[min(u),max(v)]$
每个结点的 $par$ 是所有满足 $endpos[u] \in endpos[v]$ 的 $v$ 中且 $endpos[v]$ 大小最小的状态 $v$。
有关 $par$ 的一些性质：
$min(u)=max(par[u])+1$
$par[u]$ 所表示的字符串都是 $u$ 的后缀。
自动机接受的字符串为 $S$ 的所有子串。
表示字符串前缀 $Pre$ 的状态 $u$ 的 $max(u) = |Pre|$，从 $u$ 跳 $par$ 的话可以遍历 $Pre$ 的所有后缀。
模板
1 | namespace SAM |
技巧 & 应用
求 $endpos$ 集合的大小/最大值/最小值
考虑 $par$ 树的所有节点，$endpos$ 中 含有 $i$ 的深度最大的节点一定是表示前缀 $Pre_{i}$ 的状态，标记这个节点后用 dfs/拓扑/基排 逆推即可。
如果要求每个点 $endpos$ 的具体值可能需要 线段树合并/平衡树启发式合并。
1 | int seq[MAXN*2],buc[N]; |
$logn$ 查找某个子串在 $SAM$ 上对应的状态
考虑倍增，预处理出每个节点在 $par$ 树上的$2^j$ 祖先，从表示 $S[1…r]$ 的叶子往上跳找到深度最小且满足 $max(u)>=(r-l+1)$的 $u$ 即可。
1 | void init() |
两个串的LCS
对 $S$ 串建立 $SAM$，拿 $T$ 串到 $SAM$ 上“运行”
具体来讲就是考虑 $T$ 的每个前缀 $pre_{i}$ 有多长的后缀是 $S$ 的一个子串，从 $pre_{i}$ 转移到 $pre_{i+1}$ 时看下当前状态是否存在到 $T[i+1]$ 的转移边，若不存在就不断跳 $par$ (删掉前面的一部分) 直到找到存在转移边的状态，同时维护在每个状态下的匹配长度，最后取个 $max$ 就是答案。
匹配过程十分类似于 $kmp$ 和 $AC$自动机 啊，，，
1 | void solve(char s[]) |
本质不同的子串个数
相同的子串一定被同一个状态所表示，所以对后缀自动机上每个状态所表示的子串长度求和即是答案。
最小表示法
先将字符串 $S$ 复制一倍后得到 $T$，可以发现 $T$ 的长度为 $n$ 的子串包含了 $S$ 通过循环移位所能得到的所有字符串，所以问题转化为求 $T$ 的长度为 $n$ 的子串中字典序最小的一个。
对 $T$ 建立 $SAM$ 后从 $root$ 开始贪心走转移边中字符最小的那条即可。
字典序k大子串
统计出在每个状态通过转移边能到达的状态的数量 $f[u]$ ，从根节点开始从小到大枚举转移边 $v$ 若 $f[v]>=k$ 则从 $u$ 转移到 $v$，否则将 $k$ 减去 $f[v]$ 后继续尝试字符更大的转移边。
1 | void print(int cur,int k,int t,LL f[]) |
多个串的LCS
对其中一个串建立 $SAM$ 把剩下所有串放到 $SAM$ 上运行，类似于求两个串的 $LCS$ 的过程，运行每一个串的时候记录它在当前状态上的最大匹配长度，注意不同串在同一个状态上的匹配长度要取 $min$,最后统计答案即可。
1 | void run(string &s,int id) |
广义SAM
将 $SAM$ 推广到字典树上的产物，目前不太理解，，，
定义 $Trie$ 树的一个子串为节点 $u$ 到它子树中的节点 $v$ 的路径所形成的字符串，那么广义 $SAM$ 接受的状态为 $Tire$ 树上的所有子串。
$endpos$ 可视为 $Trie$ 树上的节点，$par$ 的定义不变。
模板
离线构造，需要预先知道 $Tire$ 树的形态，从根节点开始 $bfs$，建立新节点时拿他父亲的状态作为 $last$ 执行普通 $SAM$ 的 $extend$ 即可。
还有一种做法是每插入一个串就把 $last$ 指向 $root$，但这样可能建出一些无用的节点(考虑一个字符串完全包含另一个的情况)。
[ZJOI2015]诸神眷顾的幻想乡 求多个串本质不同的子串个数
1 | const int K = 10; |
练习
Luogu P3804 【模板】后缀自动机
统计每个状态 $u$ 的 $endpos$ 集合的大小 $siz[u]$，所有的 $siz[u]*len[u]$ 取个 $max$ 就是答案1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90namespace SAM
{
int cnt=0,root,last;
int len[MAXN*2],par[MAXN*2];
LL sum[MAXN*2];
map<char,int> nx[MAXN*2];
void debug()
{
cout << dbgs2(root,last) << endl;
for(int i=1;i<=cnt;i++)
{
cout << dbgs3(i,len[i],par[i]) << endl;
for(auto t:nx[i])
cout << dbgs2(t.fi,t.se) << endl;
}
cout << endl;
}
void newnode(int &x)
{
x=++cnt;
len[cnt]=par[cnt]=sum[cnt]=0;
nx[cnt].clear();
}
void init(){cnt=0,newnode(root),last=root;}
void extend_sam(char c)
{
int cur;
newnode(cur);
len[cur]=len[last]+1;
int p=last;
while(p&&!nx[p][c])
nx[p][c]=cur,p=par[p];
if(!p) par[cur]=root;
else
{
int q=nx[p][c];
if(len[q]==len[p]+1) par[cur]=q;
else
{
int n;
newnode(n);
len[n]=len[p]+1;
par[n]=par[q];
nx [n]=nx [q];
while(p&&nx[p][c]==q)
nx[p][c]=n,p=par[p];
par[q]=par[cur]=n;
}
}
last=cur,sum[cur]=1;
}
void build_sam(char s[])
{
int n=strlen(s+1);
for(int i=1;i<=n;i++)
extend_sam(s[i]);//,debug();
}
};
char s[MAXN];
struct edge{int u,v,next;};
vector<edge> e={edge()};
int pre[MAXN*2];
void addedge(int u,int v){e.pb({u,v,pre[u]}),pre[u]=e.size()-1;}
LL ans=0;
void dfs(int u)
{
go(u) dfs(v),SAM::sum[u]+=SAM::sum[v];
//cout << dbgs3(u,SAM::len[u],SAM::sum[u]) << endl;
if(SAM::sum[u]>1) ans=max(ans,SAM::len[u]*SAM::sum[u]);
}
void solve()
{
fp(i,2,SAM::cnt)
addedge(SAM::par[i],i);
dfs(1);
}
int work()
{
scanf("%s",s+1);
SAM::init();
SAM::build_sam(s);
solve();
printf("%lld\n",ans);
return 0;
}
Luogu P1368 工艺
求字符串的最小表示法
1 | namespace SAM |
统计 $endpos$ 集合的大小，找到最大的 $sum[i]*len[i]$ 即可。
1 | namespace SAM |
SPOJ 1811 LCS
两个串的 $LCS$
1 | namespace SAM |
Luogu P3649 [APIO2014]回文串
马拉车 + SAM上倍增 其实是PAM模板题
首先考虑如何用马拉车求出本质不同的回文串，可以发现当扩展最长回文串的右边界时才会产生新的回文串，用 $SAM$ 统计出现次数即可。
注意扩展右边界时得到的回文串不一定就在之前从未出现过，如 $abadeaba$，所以用马拉车求本质不同回文串需要配上 $hash$ 来去重。
1 | namespace SAM |
Luogu P4070 [SDOI2016]生成魔咒
题意：求给定字符串每个前缀的本质不同子串个数
扩展 $SAM$ 时加上新节点的贡献即可。
1 | namespace SAM |
Luogu P3975 [TJOI2015]弦论
K小子串
1 | namespace SAM |
Luogu P2463 [SDOI2008]Sandy的卡片
多个串LCS
1 | namespace SAM |
BZOJ 1396 识别子串
设每个位置 $i$ 的最短识别子串长度为 $len[i]$
考虑那些 $endpos$ 集合大小为 $1$ 的叶子节点 $u$，设它唯一的 $endpos$ 为 $i$，则这个节点对每个位置的贡献可分两种情况讨论：
满足 $j\in[i-min(u) + 1,i]$ 的 $len[j]$ 和 $min(u)$ 取 $min$
满足 $j\in[1,i-min(i)]$ 的 $len[j]$ 和 $i-j+1$ 取 $min$
考虑两种情况分别用线段树维护，那么第一种状态的更新相当于区间每个数对 $min(u)$ 取 $min$，第二种更新 $i-j+1$ 中的 $j$ 可以提出来，同样的做法维护最小的 $i+1$ 即可。
1 | struct sgt |
Luogu P3346 [ZJOI2015]诸神眷顾的幻想乡
由于叶子最多只有 $20$ 个，我们可以把每个叶子当作根跑出一颗 $Trie$ 出来，那么 20 个 $Trie$ 合并起来就包含了所有原树上任意两个路径所构成的字符串
然后建立广义 $SAM$，最后在求一波本质不同子串即可
代码见上面
BZOJ 3277 串
贴个别人的题解，，，
1 | int n,k; |
CF235C Cyclical Quest
题意：
当两个字符串可以通过循环移位变成完全一样时我们称这两个字符串“相等”。
给定文本串，多个模式串，询问文本串中与模式串“
相等”的子串有多少
SOL：先对文本串建立 $SAM$，考虑计算模式串的所有循环移位在文本串中的出现次数
把模式串拿到 $SAM$ 上运行并记录在每个状态的匹配长度 L，每次去掉首字母并把他加到字符串末尾，若 $L-1<min(u)$ 或没有转移边就暴力跳 $par$即可。
1 | namespace SAM |
我整个人都自动机辣