#Paho110. 5.字符串查询

5.字符串查询

5.字符串查询

题目描述

小明有n个字符串S1,S2…S2S_1,S_2 \dots S_2,小红有一个字符串集合T,一开始集合是空的。 接下来会发生q个操作,操作有两种形式:

“1 P”,小红往集合T里添加了一个字符串P。

“2 x”,小明询问小红,集合T中有多少个字符串包含串SxS_x。(我们称串A包含串B,当且仅当B是A的子串)。

小红遇到了困难,需要你的帮助。

输入格式

第一行,一个数n。

接下来n行,每行一个字符串表示SiS_i。

接下来下一行,一个数q。

接下来q行,每行一个操作,格式见题目描述。

输出格式

对于每一个小明的询问,帮小红输出答案。

数据范围

(原站未提供,导入后需人工补齐)

样例

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

提示

对于100%的数据:$1<=N,Q<=100000,\sum s\in S|s| ,\sum s\in T|s|<=2*10^6$。