题面描述
给定n个模板串，以及m个查询串，查询每一个查询串是多少个模板串的子串
题解
广义后缀自动机匹配和子树数颜色，后者用启发式合并即可
广义后缀自动机的拓扑序又双叒叕挂掉了，上次口胡的解决方法错了，我不想建树啊，谁来救救蒟蒻啊啊啊啊
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
using namespace std;
const int N = 2e5+5;
int n, q;
char s[N];
int ch[N][26], tot = 1, last = 1, fa[N], len[N], size[N];
int tax[N], p[N];
set<int> f[N];
vector<int> son[N];
inline void insert(int c)
{
int cur = ++tot, pre = last; last = cur;
len[cur] = len[pre]+1;
while(pre&&!ch[pre][c]) ch[pre][c] = cur, pre = fa[pre];
if(!pre) return void(fa[cur] = 1);
int x = ch[pre][c];
if(len[pre]+1 == len[x]) return void(fa[cur] = x);
int y = ++tot; fa[y] = fa[x]; fa[x] = fa[cur] = y; len[y] = len[pre]+1;
memcpy(ch[y], ch[x], sizeof(ch[x]));
while(pre&&ch[pre][c] == x) ch[pre][c] = y, pre = fa[pre];
}
void dfs(int x)
{
for(int i = 0; i < son[x].size(); ++i)
{
int y = son[x][i]; dfs(y);
if(f[x].size() < f[y].size()) swap(f[x], f[y]);
f[x].insert(f[y].begin(), f[y].end()); f[y].clear();
}
size[x] = f[x].size();
}
int main()
{
scanf("%d%d", &n, &q);
for(int i = 1; i <= n; ++i)
{
scanf("%s", s); last = 1;
for(int k = 0; s[k]; ++k) insert(s[k]-'a'), f[last].insert(i);
}
for(int i = 2; i <= tot; ++i) son[fa[i]].push_back(i); dfs(1);
while(q--)
{
scanf("%s", s);
int x = 1, lcs = 0, strl = 0;
for(int i = 0; s[i]; ++i)
{
while(x&&!ch[x][s[i]-'a']) x = fa[x], lcs = len[x];
if(!x) x = 1, lcs = 0;
else x = ch[x][s[i]-'a'], ++lcs;
++strl;
}
printf("%d\n", size[x]*(lcs == strl));
}
return 0;
}