题意
题目链接
Sol
广义后缀自动机板子题。。和BZOJ串那个题很像
首先建出询问串的SAM，然后统计一下每个节点被多少个串包含
最后直接拿询问串上去跑就行了
代码语言：javascript复制#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("%dn", flag == 1 ? 0 : val[now]);
}
return 0;
}
