后缀自动机 专题训练

发布于 2018-01-29  5.2k 次阅读


又是一个非常强大的字符串算法。具体讲解我感觉最好看一看2015年的论文以及wmd对俄文讲解的翻译,放一些有用的资料:

后缀自动机:O(N)的构建及应用

后缀自动机(SAM)学习笔记

国家集训队2015论文集-71-83.pdf

 

明确几个概念以及性质:

1.right集合:一个子串在字符串中出现位置的所有右端点的集合。right集合的大小即为parent树中该节点子树接受态的数量,也就是这个子串在原串中的出现次数。

2.parent树:由right集合要么包含要么不相交的性质,构建出的一棵树。树边也就是“后缀链接”,父亲节点是儿子所代表子串的最长后缀。

3.最大最小长度:该right集合所代表的最长/最短的子串的长度,每个节点最小长度是parent树中父亲的最大长度+1。每个right集合对于总共出现的本质不同子串的贡献,就是该right集合最大与最小长度之差(父节点代表最长后缀,那么新产生的子串就是右端点固定,左端点在范围内的所有串)。

 

BZOJ3998 [TJOI2015]弦论

求本质相同或本质不同的K小子串。DP计算路径条数,本质不同的,每个点贡献就是1,否则是right集合大小。那么只要逐位确定即可。

 

BZOJ3926 [Zjoi2015]诸神眷顾的幻想乡

叶子节点<=20,对于每个叶子节点DFS一次,跑广义后缀自动机,之后查本质不同子串大小。对于广义后缀自动机,一种可行的处理方法就是除了修改last指针特殊处理外,其他操作与普通SAM相同处理。注意这样可能会使两个相同的状态搞到两个点上,但是DFS时不影响答案。

 

BZOJ2946 [Poi2000]公共串

求多个串的最长公共子串。拿出一个串来建SAM,剩下的串来跑匹配,记录每个节点匹配的长度,每次取min,最后取所有节点的最大匹配长度即可。

 

BZOJ3238 [Ahoi2013]差异

求所有后缀两两之间之间的LCP之和。两个后缀的LCP就是反串的parent树上的LCA,DFS一次统计方案数再乘上长度即可。

 

BZOJ2882 工艺

求一个串的最小循环同构。把串多插一次,贪心走字典序最小的儿子n次即可,等同于在一个串中找出一个字典序最小的子串。

 

BZOJ2099 [Usaco2010 Dec]Letter 恐吓信

给出两个串,求利用第一个串最少选出几段(可重复)才能拼出第二个串。如果我们不选择尽量靠右的失配点来切一刀,那么一定需要再切一刀,所以不优。因此只要贪心找最靠右的分割点即可。

 

BZOJ4516 [Sdoi2016]生成魔咒

每次给字符串末端插入一个字符,求当前本质不同的子串总数。从right集合的性质入手,每次的增量是右端点为当前点,左端点在right集合最大最小长度之间的串,也就是len[np]-len[fa[np]]。

 

BZOJ2555 SubString

要求末端插入一个字符串,查询某个字符串在原串中的出现次数,强制在线。

字符串的出现次数就是对应right集合的大小,用LCT动态维护每个点的right集合大小就好了。

(感觉这题我写丑了,跑得很慢)

 

BZOJ2806 [Ctsc2012]Cheat

题意略。用SAM预处理每个点向左的最大匹配长度,之后二分答案+DP验证。设f[i]:前i个字符,在满足当前二分长度的限制下的最大匹配长度,那么f[i]=max(f[i-1],f[j]+i-j) (mxl[i]-1<=j<=i-x),可以用单调队列优化,直接上的话只有70分。

 


Narcissus | HZOIer | zhuohaoyu1228@gmail.com | QQ 943382974