【模板】AC自动机（二次加强版）

模板

(Problem：) 求 (n) 个模式串在文本串中出现的次数
(templete：) (Luogu5357)

(Code)

#include<cstdio>
#include<cstring>
using namespace std;

const int N = 2e5 + 5;
int tr[N][26] , sum[N * 26] , id[N * 26] , tag[N * 26] , fail[N * 26] , q[N * 26] , ans[N] , map[N];
int n , tot;
char s[2000005];

void insert(int x)
{
	int len = strlen(s) , u = 0;
	for(register int i = 0; i < len; i++)
	{
		int ch = s[i] - 'a';
		if (!tr[u][ch]) tr[u][ch] = ++tot;
		u = tr[u][ch];
	}
	if (!id[u]) id[u] = x;
	map[x] = id[u];
}

void get_fail()
{
	int h = 0 , t = 0;
	for(register int i = 0; i < 26; i++) if (tr[0][i]) q[++t] = tr[0][i];
	while (h < t)
	{
		int now = q[++h];
		for(register int i = 0; i < 26; i++)
		{
			if (!tr[now][i]) {tr[now][i] = tr[fail[now]][i]; continue;}
			fail[tr[now][i]] = tr[fail[now]][i];
			++tag[tr[fail[now]][i]] , q[++t] = tr[now][i];
		}
	}
}

void calc()
{
	int len = strlen(s) , u = 0;
	for(register int i = 0; i < len; i++)
		u = tr[u][s[i] - 'a'] , ++sum[u];
	int h = 0 , t = 0;
	for(register int i = 1; i <= tot; i++) 
	if (!tag[i]) ans[id[i]] = sum[i] , q[++t] = i;
	while (h < t)
	{
		int now = q[++h] , k = fail[now];
		--tag[k] , sum[k] += sum[now] , ans[id[k]] = sum[k];
		if (!tag[k]) q[++t] = k;
	}
}

int main()
{
	scanf("%d" , &n);
	for(register int i = 1; i <= n; i++) scanf("%s" , s) , insert(i);
	get_fail();
	scanf("%s" , s) , calc();
	for(register int i = 1; i <= n; i++) printf("%d
" , ans[map[i]]);
}