后缀自动机经典操作

看了几天的后缀自动机，感觉这玩意儿确实比较神奇。但是感觉自己肯定讲不明白，就简单的来写写心得和应用吧

性质

1、每个状态$s$代表的长度区间为$(len[fa[s]],len[s])$

也就是说$min(s) = max(s) + 1$

 

2、每个状态$s$代表的所有串在原串中的出现次数及出现位置右端点相同。

这也是后缀自动机能够压缩状态的原因，就是把很多相同的串压缩到一个节点中

 

3、在parent树中，对于状态$s$，$fa[s]$所代表的状态是$s$所代表状态的后缀

 

4、在parent树中，每个状态的$right$集合是它父节点$right$集合的子集

由性质$3$很容易得到$fa[s]$所代表的状态是$s$所代表状态的后缀，那么$fa[x]$所代表的子串的出现位置一定比$s$代表子串的出现位置多

 

5、对转移边形成的DAG拓扑排序后，每个节点对应的大小为：以该节点为起点的子串的数量（本质相同的子串算一个）

 

6、对$fa$边形成的树拓扑排序后，每个节点对应的大小为该节点对应$right$集合的大小

$fa[s]$表示的是$s$的前缀，那么$s$出现的地方$fa[s]$也一定出现

 

经典应用

求两个串的最长公共子串

首先把第一个串的SAM建出来，

枚举第二个串，同时沿着转移边进行匹配，若匹配失败，那么就沿着$fa$边向上走，

匹配的同时记录一下$max$

SPOJ1811 LCS 

求多个串的最长公共子串

网上的做法基本都是对第一个串建SAM，然后枚举其他的串，在这个串上匹配。

但是貌似要考虑很多东西？？

这里我将一个比较naive但是不会TLE的做法。

最终的答案一定出现在第一个串中，所以可以把第$2-N$个串的SAM建出来

然后枚举第一个串的每一位，在其余的SAM中匹配。

虽然听着吓人，但是代码十分好写

BZOJ2946 [Poi2000]公共串

求第$k$小子串

我们可以通过对转移边$dfs$而求出以该节点为起点的子串的大小

开始时从$root$开始走，每次优先选择字典序小的转移边，

若该出边对应的大小$<k$，说明答案不在该出边所对应的字符串中，令$k$减去该节点的大小，继续匹配

若该出边对于的大小$>=k$，说明答案在该出边中，那么沿着该出边继续走

 

注意在求第$k$小子串的时候要考虑本质相同的子串是否重复统计的问题

如果要重复统计，则加上$right$集合的大小就可以了

 

不重复统计SPOJ7258 SUBLEX

重复统计BZOJ3998: [TJOI2015]弦论

 

字符串最小表示法

最小表示法的定义：

字符串$S$的最小表示法为，对于任意的$i \in [1, |S|]$，把$[1,i]$对应的字符串剪切到$S$尾所形成的字符串中，字典序最小的一个

 

字符串的最小表示有它自己的算法，可以参考这里

当然后缀自动机也是可以搞的，我们首先把字符串复制一遍，扔到SAM里，

然后从根节点出发贪心的走较小的出边，同时输出每一次经过的字符，当达到$N$次时停止。

 

但是我还是建议大家学一下最小表示法的标准算法， 因为后缀自动机需要$4*|S|*siz$的空间($siz$表示字符集)，很容易被卡掉

POJ1509 Glass Beads

 

求本质不同的串的数量

考虑到每个状态表示的子串是两两不同的，

根据性质1每个状态$s$代表的长度区间为$(len[fa[s]],len[s]]$

然后对所有节点求个和就好，答案为$\sum_{t} len[t] - len[fa[t]]$

 

标签：

版权申明：本站文章部分自网络，如有侵权，请联系：west999com@outlook.com
特别注意：本站所有转载文章言论不代表本站观点，本站所提供的摄影照片，插画，设计作品，如需使用，请与原作者联系，版权归原作者所有