bzoj#P3881. [Coci2015] Divljak

[Coci2015] Divljak

题目描述

Alice 有 nn 个字符串 S1,S2...SnS_1,S_2...S_n,Bob 有一个字符串集合 TT,一开始集合是空的。

接下来会发生 qq 个操作,操作有两种形式:

  1. 1 P,Bob 往自己的集合里添加了一个字符串 PP
  2. 2 x,Alice 询问 Bob,集合 TT 中有多少个字符串包含串 SxS_x。(我们称串 AA 包含串 BB,当且仅当 BBAA 的子串)

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

输入格式

第一行,一个数 nn

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

下一行,一个数 qq

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

输出格式

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

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

数据规模与约定

对于 100%100\% 的数据,1n,q1051 \le n,q \le 10^5

Alice 和 Bob 拥有的字符串长度之和各自都不会超过 2×1062\times 10^6

字符串都由小写英文字母组成。

题目来源

鸣谢 Dzy