【学习笔记】后缀自动机瞎学

第一次学SAM还是一年前,当时只记得怎么看怎么不会orz

$1$ 基本内容

…于是还是分条陈述

0、一个子串的 $endpos$ 集合指的是它在原串内出现的所有的右端点下标组成的集合。显然有这么一个性质,对于两个子串,它们的 $endpos$ 集合要么存在包含关系,要么没有交集。

1、首先,SAM是个自动机。转移是字符,状态是 $endpos$ 集合相同的子串。有一个起始状态,一堆终止状态,每个终止状态是原串的一个后缀。

2、如果记每个状态里面最长的子串的长度为 $L_{\max}$,最短的子串长度为 $L_{\min}$ ,那么这个状态承载的子串长度覆盖整个区间 $[L_{\min},L_{\max}]$.

3、考虑后缀链接 $\rm link$ 。$\mathrm{link}(v)$ 指向的是 $L_{\max}(u)+1=L_{\min}(v)$ 且 $endpos(v)\subset endpos(u)$ 的这么一个节点 $u$ . 可以看出,其实 $u$ 里面的子串就是 $v$ 中的子串的某些更短的后缀,但是出现次数更多。不难知道这东西是有单调性的。

4、发现后缀链接 $\rm link$ 联系起来的每个状态之间,长度单调且前驱唯一,再加上显然连通,所以 $\{\rm S,link\}$ 本质上是一棵树。

5、于是考虑怎么构造。大概就是增量构造法。

(1)每次加入一个新的状态 $np$ 时,考虑上一个转移到的状态 $p$ ,把 $L_{max}(np)$ 设置为 $L_{\max}(p) + 1$ (显然)。一直沿着后缀链接向上跳,并且把途中的转移都连向 $np$,因为原来不存在当前字母 $c_{now}$ 的转移,所以加入一个字母之后要一起改。

(2)考虑不断跳 $p$ ,直到跳到一个 $p$ 具有 $c_{now}$ 的转移,把这个转移到的状态称之为 $q$。那么此时 $endpos(q)$ 会多出一个元素,长度为 $L_{\max}(p)+1$。此时由于 $L_{\max}(p)<q$ 有两种情况需要考虑:

① $L_{\max}(q)=L_{\max}(p)+1$,这时 $q$ 代表的所有串的 $endpos$ 不变。考虑 $np$ 具有至少一个不同于 $q$ 的状态,即 $[1…now]$ ,现在插入的最长前缀。所以此时令 $\mathrm{link}(np)=q$ 而不是合并。

② $L_\max(q)>L_\max(p)+1$,这时 $q$ 中的串,长度不超过 $L_\max(p)+1$ 的串会多一个 $endpos$,即 $now$;但是大于 $L_{\max}(p)+1$ 的串则不会。所以此时需要拆开状态 。考虑为了维护一个状态里面所有点的 $endpos$ 相同,需要新建一个状态 $nq$,代表原来串中所有长度不超过 $L_\max(p)+1$ 的串。发现这么拆分的话,有

另,对于第二种情况,发现就类似抠掉一个点,换进去一颗子树。于是乎从 $p$ 开始又要不断向上跳,把所有 $trans=q$ 的点都改成 $nq$。

哦,对,树 $\{\rm S,link\}$ 有个学名叫做 $parent$ 树来着。

然后就完了,就完了……

发现其实到最后SAM十分的短:

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
struct SAM{
int last, sz ;
int trans[MAXN][Sigma] ;
int len[MAXN], fa[MAXN] ;
void Init(){ last = sz = 1 ; }
void Insert(int x){
int np = ++ sz ;
int p = last, q, nq ;
last = np, f[np] = 1 ;
len[np] = len[p] + 1 ;
while (p && !trans[p][x])
trans[p][x] = np, p = fa[p] ;
if (!p)
return fa[np] = 1, void() ;
q = trans[p][x] ;
if (len[q] == len[p] + 1)
return fa[np] = q, void() ;
nq = ++ sz,
len[nq] = len[p] + 1;
fa[nq] = fa[q], fa[q] = fa[np] = nq ;
memcpy(trans[nq], trans[q], sizeof(trans[q])) ;
while (p && trans[p][x] == q)
trans[p][x] = nq, p = fa[p] ;
}
}S;

$2$ 例题

然而有些例题就是很水。。。于是放到这里来了。。

$1$ [SDOI2016]生成魔咒

2016年SD居然考过这种有趣东西x

询问每加入一个字符时,当前整个串的本质不同子串数量。


发现在SAM里面的 $\rm link$ 树上,本质不同的子串数的增量是 $L_{\max}(now)-L_{\max}(fa)$。

于是:

1
2
3
4
5
6
7
设fa为q原来的父亲。
则原来的贡献是len(q) - len(fa)
现在的贡献是
len(nq) - len(fa) + len(q) - len(nq) + len(np) - len(nq)
= len(q) - len(a) + len(np) - len(nq)
相当于只增加了len(np) - len(nq)
SAM题 = 推式子题.jpg

然后就做完了。

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
struct SAM{
int last, sz ;
int len[MAXN], fa[MAXN] ;
map<int, int> trans[MAXN] ;
void Init(){ last = sz = 1 ; }
void Insert(int x){
int np = ++ sz ;
int p = last, q, copy ;
len[np] = len[p] + 1, last = np ;
while (p && !trans[p].count(x))
trans[p][x] = np, p = fa[p] ;
if (!p)
return fa[np] = 1, ans += 1ll * len[np], void() ;
q = trans[p][x] ;
if (len[q] == len[p] + 1)
return fa[np] = q, ans += 1ll * (len[np] - len[q]), void() ;
copy = ++ sz ;
fa[copy] = fa[q],
fa[q] = fa[np] = copy,
len[copy] = len[p] + 1 ;
// memcpy(trans[copy], trans[q], sizeof())
trans[copy] = trans[q] ;
while (p && trans[p][x] == q) trans[p][x] = copy, p = fa[p] ;
ans += 1ll * (- len[copy] + len[np]) ;
}
}S ;

$2$ LG3804【模板】SAM

给定一个只包含小写字母的字符串 $\rm S$,

请你求出 $\rm S$ 的所有出现次数不为 $1$ 的子串的出现次数乘上该子串长度的最大值。

于是发现,这个出现次数的话,可以在 $parent$ 树上直接 $dp$ 一遍。对于每个准确插入的状态,初始设置成 $1$,然后 $dp$ 即可。

1
2
3
4
5
6
7
8
9
10
11
12
void dfs(int x){
for (int k = head[x] ; k ; k = next(k))
dfs(to(k)), f[x] += f[to(k)] ;
if (f[x] > 1) ans = max(ans, f[x] * 1ll * S.len[x]) ;
}
int main(){
cin >> (In + 1) ;
N = strlen(In + 1), S.Init() ;
for (int i = 1 ; i <= N ; ++ i) S.Insert(In[i] - 'a' + 1) ;
for (int i = 2 ; i <= S.sz ; ++ i) add(S.fa[i], i) ; dfs(1) ;
cout << ans << endl ; return 0 ;
}

$3$ [USACO06DEC] Milk Patterns

找 $\rm S$ 中出现次数超过 $k$ 的最长的串的长度。

还是 $dp$ 一遍,然后就没有然后了。

我在干什么?

1
2
3
4
5
void dfs(int u){
for (int k = head[u] ; k ; k = next(k))
dfs(to(k)), f[u] += f[to(k)] ;
if (f[u] >= K) ans = max(S.len[u], ans) ;
}