模板—字符串—AC自动机（多模式串，单文本串）

模板—字符串—AC自动机（多模式串，单文本串）

Code:

#include <queue>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define N 1000010
int ch[N][26],fl[N],head[N],to[N],nxt[N],size[N],pos[N],en[N],n,ans; char str[N];
namespace AC
{
	int idx,cnt;
	void add(int a,int b) {nxt[++idx]=head[a],to[idx]=b,head[a]=idx;}
	void insert(int id,int len)
	{
		int p=0;
		for(int i=1;i<=len;i++)
		{
			if(!ch[p][str[i]-'a'])
				ch[p][str[i]-'a']=++cnt;
			p=ch[p][str[i]-'a'];
		} pos[id]=p,en[p]++;
	}
	void dfs(int p)
	{
		size[p]=1;
		for(int i=head[p];i;i=nxt[i])
			dfs(to[i]),size[p]+=size[to[i]];
	}
	void bfs()
	{
		idx=0; queue <int> q;
		for(int i=0;i<26;i++) if(ch[0][i])
			q.push(ch[0][i]),add(0,ch[0][i]);
		while(!q.empty())
		{
			int p=q.front(); q.pop();
			for(int i=0;i<26;i++)
			{
				int &v=ch[p][i];
				if(!v) {v=ch[fl[p]][i];continue;}
				fl[v]=ch[fl[p]][i],q.push(v),add(fl[v],v);
			}
		} dfs(0);
	}
	void find(int l)
	{
		int p=0;
		for(int i=1;i<=l;i++)
		{
			p=ch[p][str[i]-'a']; if(!p) return;
			for(int j=p;j&&en[j]!=-1;j=fl[j])
				ans+=en[j],en[j]=-1;
		}
	}
}
using namespace AC;
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++) scanf("%s",str+1),insert(i,strlen(str+1)); bfs();
	scanf("%s",str+1),find(strlen(str+1)),printf("%d
",ans);
}