SP8093 JZPGYZ - Sevenk Love Oimaster(广义后缀自动机)

题意

题目链接

sol

广义后缀自动机板子题。。和bzoj串那个题很像

首先建出询问串的sam，然后统计一下每个节点被多少个串包含

最后直接拿询问串上去跑就行了

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e6 + 10;
int n, q;
string s[maxn], t[maxn];
int fa[maxn], len[maxn], ch[maxn][26], tim[maxn], val[maxn], root = 1, las = 1, tot = 1;
void insert(int x) {
    int now = ++tot, pre = las; las = now; len[now] = len[pre] + 1;
    for(; pre && !ch[pre][x]; pre = fa[pre]) ch[pre][x] = now;
    if(!pre) fa[now] = root;
    else {
        int q = ch[pre][x];
        if(len[pre] + 1 == len[q]) fa[now] = q;
        else {
            int nq = ++tot; fa[nq] = fa[q]; len[nq] = len[pre] + 1;
            memcpy(ch[nq], ch[q], sizeof(ch[q])); 
            fa[q] = fa[now] = nq;
            for(; pre && ch[pre][x] == q; pre = fa[pre]) ch[pre][x] = nq;
        }
    }
}
int main() {
    cin >> n >> q;
    for(int i = 1; i <= n; i++) {
        cin >> s[i]; las = 1;
        for(int j = 0; j < s[i].length(); j++) insert(s[i][j] - 'a');
    }
    for(int i = 1; i <= n; i++) {
        string ns = s[i]; int now = root;
        for(int j = 0; j < ns.length(); j++) {
            int x = ns[j] - 'a';
            now = ch[now][x];
            for(int p = now; p && tim[p] != i; p = fa[p]) 
                tim[p] = i, val[p]++;
        }
    }
    for(int i = 1; i <= q; i++) {
        string ns; cin >> ns;
        int now = root, flag = 0;
        for(int j = 0; j < ns.length(); j++) {
            int x = ns[j] - 'a';
            if(!ch[now][x]) {flag = 1; break;}
            now = ch[now][x];
        }
        printf("%d\n", flag == 1 ? 0 : val[now]);
    }
    return 0;
}