AC自动机模板题

看到数据范围，所有单词长度不超过$10^6$，所以肯定是要拓扑排序优化的，这里我选择了DFS版的

#include<bits/stdc++.h>
#define int long long
#define push_back emplace_back
using namespace std;

int n,cnt=0;
string s[200005];
vector<vector<int> > g(200005);
struct node
{
	int son[27],fail,end,dp;
} t[200005];
void build(string s)
{
	int now=0;
	for (auto c:s)
	{
		c-='a';
		if (!t[now].son[c]) t[now].son[c]=++cnt;
		now=t[now].son[c];
	}
	t[now].end++;
}
int find(string s)
{
	int now=0;
	for (auto c:s)
		now=t[now].son[c-'a'];
	return t[now].dp;
}
void getfail()
{
	queue<int> q;
	for (int i=0;i<27;i++)
	{
		if (t[0].son[i])
			q.push(t[0].son[i]),g[0].push_back(t[0].son[i]);
	}
	while (!q.empty())
	{
		int now=q.front();
		q.pop();
		for (int i=0;i<27;i++)
		{
			if (t[now].son[i])
			{
				t[t[now].son[i]].fail=t[t[now].fail].son[i];
				g[t[t[now].fail].son[i]].push_back(t[now].son[i]);
				q.push(t[now].son[i]);
			}
			else
				t[now].son[i]=t[t[now].fail].son[i];
		}
	}
}
inline void dfs(int now)
{
	for (auto v:g[now])
		dfs(v),t[now].dp+=t[v].dp;
}
void query(string s)
{
	int now=0;
	for (auto c:s)
	{
		c-='a';
		now=t[now].son[c];
		t[now].dp++;
	}
	dfs(0);
}
signed main()
{
	cin >> n;
	for (int i=1;i<=n;i++)
	{
		cin >> s[i];
        s[0]+=s[i]+"{";
		build(s[i]);
	}
	getfail();
	query(s[0]);
	for (int i=1;i<=n;i++)
		cout << find(s[i]) << endl;
	return 0;
}