Luogu P3808 【模板】AC自动机（简单版）

模板，没太理解到呢。

Flag ：明天再打一遍。

#include<bits/stdc++.h>
using namespace std;
#define N 1000005
int n;
namespace AC
{
	int tr[N][26], tot;
	int e[N], fail[N];
	void insert(char *s)
	{
		int u = 0;
		for(int i = 1; s[i]; i++)
		{
			if(!tr[u][s[i] - 'a'])
			{
				tr[u][s[i] - 'a'] = ++tot;
			}
			u = tr[u][s[i] - 'a'];
		}
		e[u]++;
		return;
	}
	queue<int> q;
	void build()
	{
		for(int i = 0; i < 26; i++)
		{
			if(tr[0][i])
			{
				q.push(tr[0][i]);
			}
		}
		while(!q.empty())
		{
			int u = q.front();
			q.pop();
			for(int i = 0; i < 26; i++)
			{
				if(tr[u][i])
				{
					fail[tr[u][i]] = tr[fail[u]][i];
					q.push(tr[u][i]);
				}
				else
				{
					tr[u][i] = tr[fail[u]][i];
				}
			}
		}
		return;
	}
	int query(char *s)
	{
		int u = 0, ret = 0;
		for(int i = 1; s[i]; i++)
		{
			u = tr[u][s[i] - 'a'];
			for(int j = u; j && e[j] != -1; j = fail[j])
			{
				ret += e[j];
				e[j] = -1;
			}
		}
		return ret;
	}
}
char s[N];
int main()
{
	scanf("%d", &n);
	for(int i = 1; i <= n; i++)
	{
		scanf("%s", s + 1);
		AC::insert(s);
	}
	scanf("%s", s + 1);
	AC::build();
	printf("%d", AC::query(s));
	return 0;
}