Description

Alice有n个字符串S_1,S_2…S_n,Bob有一个字符串集合T,一开始集合是空的。
接下来会发生q个操作,操作有两种形式:
“1 P”,Bob往自己的集合里添加了一个字符串P。
“2 x”,Alice询问Bob,集合T中有多少个字符串包含串S_x。(我们称串A包含串B,当且仅当B是A的子串)
Bob遇到了困难,需要你的帮助。

Input

第1行,一个数n;
接下来n行,每行一个字符串表示S_i;
下一行,一个数q;
接下来q行,每行一个操作,格式见题目描述。

Output

对于每一个Alice的询问,帮Bob输出答案。

Sample Input

3
a
bc
abc
5
1 abca
2 1
1 bca
2 2
2 3

Sample Output

1
2
1

HINT

【数据范围】
1 <= n,q <= 100000;
Alice和Bob拥有的字符串长度之和各自都不会超过 2000000;
字符串都由小写英文字母组成。

Source

鸣谢 Dzy

首先将alice的集合建AC自动机 那么每次添加bob的集合的时候可以知道去ac自动机上跑一下 每个经过的节点的fail树上的那条链都需要添加一下计数器 但是这样暴力跳fail链复杂度是不对的大概最坏会是n^2的复杂度  那么相当于我需要计算链的这个并 那么就有一个神奇的做法 首先把我这次这个单词要经过的AC自动机上所有点按照dfs序排序 那么给每个点都+1 然后统计的时候直接统计该单词子树里+1的个数即可 但是可能会有重复的所以需要把lca处都-1 然后即可

 


elijahqi

退役了 现在在商院 偶尔打CF,有时有ACM regional也去玩一下

发表评论