almost 2 years ago

前言

很经典的一道题啊,想到了蛮多的做法来写一下,有别的做法的欢迎在评论里提出来...

题意

有一个模板串集合,一开始为空,每次有三种操作:
中插入一个字符串,保证不会插入集合中原有的字符串;
删除在集合中的一个字符串;
给定一个字符串,询问模板串集合中字符串出现在中的总次数,一个字符串在中出现了多次算作多次。
字符集大小,字符串总长度和
离线or在线

离线

离线我只想出了一个做法,就是考虑一个模板串出现的区间,将这个插入挂在线段树上相应的区间上,询问直接遍历一遍线段树,线段树上每个节点建一个AC自动机即可,时间复杂度
ECR 16 F(offline).cpp

在线

在线有三个做法,两个是级别的,一个是级别的。
第一个根号做法是考虑长度种类最多只有种,因此对于询问我们可以枚举长度+字符串hash解决。
第二个根号做法是考虑将长度根据分成两部分,对于长度大于的字符串个数不会超过个,因此可以暴力KMP解决,对于长度小于的字符串,我们可以对于它们建立Trie树,这样询问就分成了两部分,都是的。
在线的做法类似二进制分组,根据长度分出个形如的块,每当一个块中有超过一个自动机时,合并其中两个自动机并视情况将其提升到更高层的块中去,因为一个字符串之多被合并次,因此这样的复杂度是的。
这三种做法CF上都有相应的代码。
(然而聪明的人已经看出来了,为啥我只贴了离线的代码呢?因为原题是在线的,我没看到所以写的离线,然后...就没有然后了...)

← NOI2016游记&&感想 AIM Tech Round 3 E →
 
comments powered by Disqus