首页 > 其他 > 详细

后缀自动机做题技巧

时间:2020-09-19 10:23:53      阅读:65      评论:0      收藏:0      [点我收藏+]

后缀自动机做题技巧

①后缀自动机的总状态数小于\(2n\),总转移边数小于\(3n\)

②后缀自动机沿着 link 链接跳的总复杂度为\(O(n)\),构造后缀自动机的总复杂度也是\(O(n)\)

性质:

①插入字符新增子串数:len[p]-len[link[p]]

②后缀链接:link[p]表示的字符串是p的后缀

③沿着转移数组走,可以得到母串的所有子串。

④沿着后缀链接走,一直得到的是当前点的后缀串。

⑤如果把非clone点的cnt[i]值置为1,然后沿着后缀链接的反向边 dfs 一遍,把其子节点的贡献都加到自己身上,最后得到的cnt[i]就是 i 这个节点所表示的串在母串中出现的总次数。因为子节点的结束下标肯定是跟 i 不同的(除了clone节点),而 i 所表示的字符串是子节点表示字符串的子串,所以把贡献加以来就可以了。

⑥求第 i 个节点所表示串的出现个数(本质相同,位置不同也可):先将所有非克隆节点的cnt[i]置为1,然后在后缀树上跑 dfs ,把 i 的子树的贡献加到自己身上即可。

⑦求第 i 个节点所表示串的出现个数(本质相同,位置不同算一个串):将所有(包括克隆节点)的cnt[i]置为1即可。

后缀自动机做题技巧

原文:https://www.cnblogs.com/CADCADCAD/p/13694798.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!