后缀自动机
关注
分享
扫一扫
Deep_Kevin
这个作者很懒，什么都没留下…
展开
-
[APIO2014]回文串，LuoguP3649，后缀自动机+Manacher+倍增
正题 Portal 学后缀自动机以来第一次写的题。 强行学习Manacher之后，可以发现本质不同的字符串当len在扩张的时候才会出现，否则肯定在前面出现过。 然后现在已知一个子串，要求它的出现次数，想到后缀自动机，我们从r前缀这个等价类开始往它的link跳，因为每跳一次就会变成原来的后缀，所一直要保证长度>=len就好了，具体过程用倍...原创 2019-08-09 22:31:14 · 142 阅读 · 0 评论 -
[TJOI2015]弦论，LuoguP3917，后缀自动机
正题 Portal 考虑建出后缀自动机，在上面不断往后跑，每当trans一遍的时候，可以保证跳到的等价类一定包含s+c这个状态。 也就是说，其实通过什么途径到达当前的等价类其实并不重要。 所以就可以分情况，当t=0时，一个等价类的出现次数就是1，当t=1时，一个等价类的出现次数就是endpos集合的大小。 然后每一个节点统...原创 2019-08-09 22:36:33 · 152 阅读 · 0 评论 -
学习笔记第四十九节：后缀自动机
正题 菜就是菜。 其实真的不怎么喜欢字符串。 后缀自动机可以想象成一个函数，当一个串的后缀自动机建好的时候，你把这个串的一个后缀丢进去，他就会返回True，否则就会返回False。 先讲一些概念。状态State 把这个串的每一个子串p提出来，一个子串可能在这个串里面出现了很多次，设出现位置的右端点集合。 对于同...原创 2019-08-07 21:31:36 · 267 阅读 · 0 评论