模板

\(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\n" , ans[map[i]]);

}

巴特西

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

模板

\(Code\)

最新文章

热门文章