使用LCA+差分+树状数组+AC自动机的做法

#include<bits/stdc++.h>
#define int long long
#define N 20000006
using namespace std;
int read() {
	int x = 0, f = 1; char ch = getchar();
	while(ch < '0' || ch > '9') { if(ch == '-') f = -1; ch = getchar(); }
	while(ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); }
	return x * f;
}
void write(int x) {
	if(x < 0) putchar('-'), x = -x;
	if(x > 9) write(x / 10);
	putchar('0' + x % 10);
}
int n, Q;
int tree[N][30], fail[N], cnt = 1;
int ans[N], vis[N];
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);
        //cout << i << "->" << fail[i] << endl;
    }
}
int dfn[N], top[N], son[N], dep[N], siz[N], tot, father[N];
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]];
    }
    if(dep[x] < dep[y]) return x;
    else return y;
}
void init() {
    memset(top, -1, sizeof(top));
    dfs1(0, -1);
    dfs2(0, 0);
    //cout << "LCA : " << lca(5, 6) <<
}
int lowbit(int x) {
    return x & (-x);
}
int c[N];
void add(int x, int y) {
    for(int i = x; i <= cnt + 1; i += lowbit(i)) c[i] += y;
}
int query(int x) {
    if(x == 0) return 0;
    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);
}
int P[N], h[N], len;
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);
    //cout << "h : ";
    //for(int i = 1; i <= len; i++) cout << h[i] << " ";
    //cout << endl;
    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);
    
    for(int i = 1; i <= cnt; i++) 
        ans[i] += ask(dfn[i], dfn[i] + siz[i] - 1);
    
    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() {
    n = read();
    for(int i = 1; i <= n; i++) {
        cin >> s;
        insert(s, i);
    }
    Getfail();
    init();
    Q = read();
    while(Q--) {
        int opt = read();
        if(opt == 1) {
            string s;
            cin >> s;
            work(s);
        }
        else {
            int x = read();
            //cout << "X : " << vis[x] << endl;
            write(ans[vis[x]]);
            printf("\n");
        }
    }
    return 0;
}
/*
3
aab
aba
aba
100
1 babaabbbaa
2 2
*/

/*
3
aab
aba
aba
5
2 2
1 babaabbbaa
1 bbbbbbbbab
1 bbaabaaaba
2 2
*/