ac自动机是kmp在trie上的推广，kmp适用于单模式串匹配，而ac自动机适用于多模式串的匹配。既然是kmp在trie上的推广，我们不妨先来回忆一下kmp的核心：求next数组的过程。next[i]是与模式串前缀匹配的后缀最长的长度(也可以理解为与最长后缀匹配的前缀的下标)此处说的都是非平凡的前缀后缀。

next[0]=next[1]=0;
for(int i=2;i<=n;i++)
{
	j=next[i-1];
	while(j&&p[j+1]!=p[i]) j=next[j];
	if(p[j+1]==p[i]) j++;
	next[i]=j;
}

推广到trie树上，是基于bfs，将前面层的信息都算出来。、


int hh=0,tt=-1;
for(int i=0;i<26;i++)
	if(tr[0][i])
		q[++tt]=tr[0][i];

while(hh<=tt)
{
	int t=q[hh ++ ];
	for(int i=0;i<26;i++)
	{
		int c=tr[t][i];
		if(!c) continue;
		
		int j=next[t];
		while(j && !tr[j][i]) j=next[j];
		if(tr[j][i]) j=tr[j][i];
		next[c]=j;
		q[++tt]=c;
	}
}

同样匹配的时候我们也先看一下kmp是怎么做的

for(int i=1,j=0;i<=n;i++)
{
	while(j&&s[i]!=p[j+1]) j=ne[j];
    if(s[i]==p[j+1]) j++;
    if(j==m)
    {
    	j=ne[j];
        //匹配成功
	}
}

根据这个推广到ac自动机上:

for(int i=0,j=0;i<n;i++)
{
	int t=str[i]-'a';
	while(j&&!tr[j][t]) j=ne[j];
	if(tr[j][t]) j=tr[j][t];
	
	int p=j;
	while(p)
	{
		res+=cnt[p];
		cnt[p]=0;
		p=ne[p];
	}
}

trie图优化: 如果不存在，指向父节点next指针的对应儿子 存在的话，更新ne[c]

if(!c) tr[t][i]=tr[ne[t]][i];
else
{
	ne[c]=tr[ne[t]][i];
    q[++tt]=c;
}