后缀自动机SAM学习笔记

看起来我已经一个月没更新博客了

可能需要一个人来催我

强的人都已经早就掌握sam了啊,菜的人只能等省选讲课;

hzy讲了回文自动机后缀数组后缀自动机后缀树后缀平衡树和一大堆例题;

然后会的本来就会不会的还是不会;

(侵删)

然后强行yy了一下后缀自动机;

好了故事讲完了我们进入正题。

顾名思义SAM是一种有限状态自动机;(废话

一般用来支持对一个字符串的所有子串的查询。

我们先考虑一颗包含一个字符串的所有后缀的Tire

然后会发现大部分点都没啥用,有用的点的个数最多为2n。

证明如下:

​ 考虑加入一个后缀,最多产生一个显式节点并且使原树的一个隐式节点变为显式。

​ 闭上眼睛感受一下你会发现是对的。

如果我们把字符串倒置,那么这些后缀就变成了一堆前缀。

定义len为当前节点的最长串长,也就是在左边那个树中的深度。

然后每个点的状态就变成了,从原串的某个位置开始,长度为[len[father[x]]+1,len[x]]的某个点的前缀(当然是倒置之后了);然后感受一下发现了这个子树的所有叶子结点代表的位置都具有这个前缀。

下面再次有请灵魂画手cogito

这东西的性质非常的好,所以它是SAM的fail树(雾

毕竟啊。。你匹配失败了显然第一反应就是寻找更小的结束于i的后缀啊。

思考一下,然后感受一下。

现在我们来考虑一下后缀自动机的带权转移。

带权转移是啥?当然是选择原谅在当前串后面增加一个字符之后看看可以到达哪些点了。

毕竟是个有限状态自动机啊,

感受一下你会发现[1,3,5]能转移到的显然可以是[2,6]而显然不能是[3]。

转移失败的话考虑使用fail树将限制缩小。

考虑建立SAM:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int put(int x,int y,int last){
int dd=last;len[++kk]=y;flag[kk]=1;
while (dd&&!a[dd][x])a[dd][x]=kk,dd=fh[dd];//找到有带权转移的前缀
if (a[dd][x]){//可以转移?
int xx=a[dd][x];if (len[dd]+1!=len[xx]){
len[++kk]=len[dd]+1;fh[kk]=fh[xx];
while (a[dd][x]==xx)a[dd][x]=kk,dd=fh[dd];//更新转移
for (int i=0;i<26;i++)a[kk][i]=a[xx][i];
//考虑把隐式节点变成显式我们只要将原先的儿子复制一份就可以了
fh[xx]=fh[kk-1]=kk;return kk-1;
}else fh[kk]=xx;
}else fh[kk]=dd,a[dd][x]=kk;//根本没这个转移啊连根节点都没有只好新建一个了
return kk;
}

对于在当前字符串末s[n]加入一个字符x的操作。

我们需要找到对于s[n-1]的对于x字符的带权转移。

然后我们就可以找到在树上对s[n]的lcp了,如果是隐式节点我们把它变成显式。然后对它连一个孩子[n]。

当你跳fail的时候那些辣鸡节点没有带权转移的时候你要把当前要加入的子串变成它们的带权转移。

具体实现可以看一下代码。

广义SAM就先留坑(逃

广告:有不详细的地方或者在下写错的地方,欢迎加qq445033901来d飞我哥。

分享到