题目大意
维护一个字符串集合,支持3种操作
- 插入一个字符串
- 删除一个字符串
- 给定一个模板串,求集合中的字符串出现次数
操作次数 $n\le 3\times10^5$ ,字符串总长度 $len\le3\times10^5$
思路
在2013年的国家集训队论文中提到了一种二进制分组的算法,即将每组询问按二进制分组,如:
$$
23=16+4+2+1\24=16+8
$$
对于每一次插入字符串,就新建一个大小为1的分组,如果大小与上一个分组一样就依次暴力合并
因为这题需要求解字符串匹配次数,所以需要对于每一个分组构建一个AC自动机
合并分组的时候暴力重构所有的节点
删除操作和插入操作是独立的,所以可以再建一个二进制分组的AC自动机,答案减一下就可以
需要注意几个细节:
- 因为我是对于每一个分组都建一个AC自动机,所以需要动态分配内存防止MLE
- 在合并两个AC自动机的时候不能直接修改每个节点的 $next$ ,因为之前会构建 $Fail$ 失配指针导致修改 $next$ ,所以最好再建一个新的 $Next$ 数组保存原本的 $next$ 数组
- 答案可以全部存到一个点上,不要暴力跳来记录答案
代码
1 | /*************************************************************** |