题意：
Alice 有 \(n\) 个字符串 \({S}_1, {S}_2, \ldots, {S}_n\)，Bob 有一个字符串集合 \({T}\)，一开始集合是空的。
接下来会发生 \(q\) 个操作，操作有两种形式：
1 P：Bob 往自己的集合里添加了一个字符串 \({P}\)。2 x：Alice 询问 Bob，集合 \({T}\) 中有多少个字符串包含串 \({S}_x\)（我们称串 \({A}\) 包含串 \({B}\)，当且仅当 \({B}\) 是 \({A}\) 的子串）。
分析：
需要支持询问一个模式串被多少个文本串包含，不如从操作 1 入手，由于模式串最开始就给出了，我们可以考虑计算添加一个文本串后包含了哪些模式串，给这些模式串的答案加 1 即可。
因此可以对模式串建立 AC 自动机，然后扫一遍 \(P\)，并暴力跳 \(fail\)，这样只能保证一个操作字典树里的每个点只经过一次，不能保证 \(P\) 只经过一次。
考虑如何优化，一个很套路的思路是连边 \(i \rightarrow fail_{i}\) 以建立一棵树，然后会产生一条从 \(P\) 中扫到的一个点在字典树上的位置到根节点的路径，扫完 \(P\) 后，把在路径并上的点的答案加 \(1\)。
现在问题转化成求路径并了，一种简单的方法是把点按照 DFS 序排序，然后将 \([h_{i+1} \rightarrow lca(h_{i},h_{i+1}) ] (i < n)\) 这条路径加 \(1\)，然后 \([h_{n} \rightarrow root]\) 这条路径加 \(1\)。
可以使用差分，这样就只用树状数组了！
代码：
#include<bits/stdc++.h>
#define int long long
#define N 2000006
using namespace std;
int n, Q, tree[N][30], fail[N], cnt = 1, c[N], ans[N], vis[N], dfn[N], top[N], son[N], dep[N], siz[N], tot, father[N], P[N], h[N], len;
string s;
void insert(string s, int x) {
int now = 1, len = s.length();
for(int i = 0; i < len; i++) {
if(!tree[now][s[i] - 'a']) tree[now][s[i] - 'a'] = ++cnt;
now = tree[now][s[i] - 'a'];
}
vis[x] = now;
}
vector<int>p[N];
void Getfail() {
for(int i = 0; i < 26; i++) tree[0][i] = 1;
fail[1] = 0;
queue<int>Q;
Q.push(1);
while(!Q.empty()) {
int x = Q.front();
Q.pop();
for(int i = 0; i < 26; i++) {
int y = tree[x][i];
if(!y) { tree[x][i] = tree[fail[x]][i]; continue; }
fail[y] = tree[fail[x]][i];
Q.push(y);
}
}
for(int i = 1; i <= cnt; i++) {
p[i].push_back(fail[i]);
p[fail[i]].push_back(i);
}
}
void dfs1(int x, int fa) {
father[x] = fa; siz[x] = 1; dfn[x] = ++tot;
if(x != 0) dep[x] = dep[fa] + 1;
else dep[x] = 1;
int Maxson = -1;
for(auto y : p[x]) {
if(y == fa) continue;
dfs1(y, x);
siz[x] += siz[y];
if(siz[y] > Maxson) {
Maxson = siz[y];
son[x] = y;
}
}
}
void dfs2(int x, int topf) {
top[x] = topf;
if(!son[x]) return;
dfs2(son[x], topf);
for(auto y : p[x]) {
if(top[y] != -1) continue;
dfs2(y, y);
}
}
int lca(int x, int y) {
while(top[x] != top[y]) {
if(dep[top[x]] < dep[top[y]]) swap(x, y);
x = father[top[x]];
}
return dep[x] < dep[y] ? x : y;
}
int lowbit(int x) { return x & (-x); }
void add(int x, int y) { for(int i = x; i <= cnt + 1; i += lowbit(i)) c[i] += y; }
int query(int x) { int res = 0; for(int i = x; i; i -= lowbit(i)) res += c[i]; return res; }
int ask(int L, int R) { return query(R) - query(L - 1); }
bool cmp(int x, int y) { return dfn[x] < dfn[y]; }
void work(string s) {
int now = 1, L = s.length(); len = 0;
for(int i = 0; i < L; i++) {
now = tree[now][s[i] - 'a'];
h[++len] = now;
}
sort(h + 1, h + len + 1, cmp);
for(int i = 1; i <= len; i++) add(dfn[h[i]], 1);
for(int i = 1; i < len; i++) add(dfn[lca(h[i], h[i + 1])], -1);
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
cin >> n;
for(int i = 1; i <= n; i++) {
cin >> s;
insert(s, i);
}
Getfail();
memset(top, -1, sizeof(top)); dfs1(0, -1); dfs2(0, 0);
cin >> Q;
while(Q--) {
int opt; cin >> opt;
if(opt == 1) {
string s;
cin >> s;
work(s);
}
else {
int x; cin >> x;
cout << ask(dfn[vis[x]], dfn[vis[x]] + siz[vis[x]] - 1) << endl;
}
}
return 0;
}