[COCI2015] Divljak
题目描述
Alice 有 $n$ 个字符串 ${S}_1, {S}_2, \ldots, {S}_n$,Bob 有一个字符串集合 ${T}$,一开始集合是空的。
接下来会发生 $q$ 个操作,操作有两种形式:
1. `1 P`:Bob 往自己的集合里添加了一个字符串 ${P}$。
2. `2 x`:Alice 询问 Bob,集合 ${T}$ 中有多少个字符串包含串 ${S}_x$(我们称串 ${A}$ 包含串 ${B}$,当且仅当 ${B}$ 是 ${A}$ 的子串)。
输入输出格式
输入格式
第一行一个整数 $n$。
接下来 $n$ 行,第 $i$ 行一个字符串 ${S}_i$。
接下来一行一个整数 $q$。
接下来 $q$ 行,每行一个操作。
输出格式
对每个 `2 x` 操作,一行一个整数,表示答案。
输入输出样例
输入样例 #1
3
a
bc
abc
5
1 abca
2 1
1 bca
2 2
2 3
输出样例 #1
1
2
1
说明
对于 $100\%$ 的数据,$1 \leq n,q \leq 10^5$,字符串由小写字母构成,$S$ 和 $P$ 的总长分别 $\le 2 \times 10^6$。