传送门
这主要想说一下AC自动机加上拓扑排序。
当我们建完AC自动机后，查询的时候会因为跳好多次fail指针而超时，所以需要优化。
为了说话方便，假设我们已经建好了fail树。
在匹配的时候，如果匹配到节点(u)，那么(u)的所有祖先代表的前缀一定能匹配上（fail指针的性质），暴力的做法是把(u)到fail树根的路径的所有点都更新一遍。但想一想就知道，可以只更新点(sum[u])，最后再从树叶往上更新一遍，即(sum[v]= sum sum[u])（(u)是(v)的儿子节点）。
优化的思路就是这样，但其实我们不用把fail树建出来，而利用一个性质：一个节点如果能被更新，那么他的孩子节点肯定已经更新完了。所以记录每一个点孩子个数（度数），然后利用拓扑排序就可以解决。
题目中可能有重复的模板串，所以每一个节点开了一个vector，用来存是哪一个模板串的结尾。
#include<cstdio>
#include<iostream>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<cctype>
#include<vector>
#include<queue>
using namespace std;
#define enter puts("")
#define space putchar(' ')
#define Mem(a, x) memset(a, x, sizeof(a))
#define In inline
typedef long long ll;
const int maxn = 2e6 + 5;
const int maxN = 6e6 + 5;
In ll read()
{
ll ans = 0;
char ch = getchar(), las = ' ';
while(!isdigit(ch)) las = ch, ch = getchar();
while(isdigit(ch)) ans = (ans << 1) + (ans << 3) + ch - '0', ch = getchar();
if(las == '-') ans = -ans;
return ans;
}
In void write(ll x)
{
if(x < 0) x = -x, putchar('-');
if(x >= 10) write(x / 10);
putchar(x % 10 + '0');
}
int n;
char s[maxn];
int ch[maxN][26], f[maxN], num[maxN], cnt = 0;
vector<int> pos[maxN];
In void Clear(int x) {Mem(ch[x], 0), f[x] = num[x] = 0;}
In int C(char c) {return c - 'a';}
In void insert(char* s, int id)
{
int m = strlen(s), now = 0;
for(int i = 0; i < m; ++i)
{
int c = C(s[i]);
if(!ch[now][c]) Clear(++cnt), ch[now][c] = cnt;
now = ch[now][c];
}
num[now] = 1; pos[now].push_back(id);
}
int du[maxN];
In void build()
{
queue<int> q;
for(int i = 0; i < 26; ++i) if(ch[0][i]) q.push(ch[0][i]);
while(!q.empty())
{
int now = q.front(); q.pop();
for(int i = 0; i < 26; ++i)
if(ch[now][i])
{
f[ch[now][i]] = ch[f[now]][i], q.push(ch[now][i]);
du[f[ch[now][i]]]++; //更新度数
}
else ch[now][i] = ch[f[now]][i];
//这个else在拓扑中没有用，但是匹配的时候如果不加这一句可能会超时。
}
}
int sum[maxn];
In void query(char* s)
{
int len = strlen(s), now = 0;
for(int i = 0; i < len; ++i)
{
int c = C(s[i]);
now = ch[now][c]; sum[now]++;
}
}
int ans[maxn];
In void topo()
{
queue<int> q;
for(int i = 0; i <= cnt; ++i) if(!du[i]) q.push(i);
while(!q.empty())
{
int now = q.front(), v = f[now]; q.pop();
for(int i = 0; i < (int)pos[now].size(); ++i) ans[pos[now][i]] = sum[now];
sum[v] += sum[now];
if(!--du[v]) q.push(v);
}
}
int main()
{
n = read(); Clear(0);
for(int i = 1; i <= n; ++i)
{
scanf("%s", s);
insert(s, i);
}
build();
scanf("%s", s);
query(s), topo();
for(int i = 1; i <= n; ++i) write(ans[i]), enter;
return 0;
}