AC自动机总结

本篇适合看完大佬博客有一定基础，但又问题重重的童鞋进来。

以下分享的都是我自己对AC自动机的感悟，不喜勿喷，就当是给我自己看的。

---

算法基本思路：Trie树上做KMP

定义

1. 若根节点到x节点这条字符串，为根节点到i节点这条字符串中最长的后缀,则fail[i]=x。
2. 根节点到当前节点i表示的字符串记为s1，根节点到fail[i]节点表示的字符串记为s2。

---

实现

插入准备匹配的串

就是普通trie树的插入，没有任何变化。

void insert()
{
	int len=s.size(),k=0;//k为当前节点的编号 
	for(int i=0;i<len;i++)
	{
		if(!trie[k].nx[s[i]-'a'])//如果没有对应字符的节点，就新建一个节点 
		trie[k].nx[s[i]-'a']=++tot;
		k=trie[k].nx[s[i]-'a'];//走到下一个节点 
	}
	trie[k].end++;//以当前字符结尾的单词数目加1 
}

求fail数组

用bfs，逐层拓展节点，确保i在确定fail指针的指向时，应该成为fail[i]的那个节点已经被遍历过了。

如何确定fail指针的指向呢？设当前节点为i，那么i节点的表示字符a的儿子，它的fail指针，应该指向fail[i]这个节点的表示a的儿子。

其实容易理解。已知s2为s1的最长后缀，那么s2+a显然还是s1+a的最长后缀。按照fail数组的定义，以上结论显然成立。

那如果i节点根本没有表示字符a的儿子，那么通过fail数组的回退，指针最终还是会指向fail[i]的表示a的儿子。那么，我们不如直接在i与fail[i]的表示a的儿子连一条边，让它直接成为i的儿子，避免不必要的回退。

void bfs()
{
	queue<int> q;
	for(int i=0;i<26;i++)
	if(trie[0].nx[i])//将第二层的节点全部入队，准备拓展 
	q.push(trie[0].nx[i]);//本来应该将第二层节点的fail指针全部赋值为根节点的，但根节点编号就为0 
	while(!q.empty())
	{
		int p=q.front();
		q.pop();
		for(int i=0;i<26;i++)
		{
			int t=trie[p].nx[i];
			if(t)//如果有当前字符的儿子 
			{
				fail[t]=trie[fail[p]].nx[i];
			//将儿子的fail指针指向((当前节点的fail指针指向的节点)表示相同字符的儿子)
				q.push(t);//将儿子入队 
			}
			else 
			trie[p].nx[i]=trie[fail[p]].nx[i];
			//否则，将((当前节点的fail指针指向的节点)表示相同字符的儿子)变为自己的儿子 
		}
	}
}

匹配：

保持当前节点的字符，永远与模式串正在匹配的字符保持匹配。
（哪怕当前节点根本不存在这个字符，这一点可能很难理解。因为如果当前节点没有这个字符，那么指针会指向0，这正是根节点的编号，相当于重新从根节点开始匹配）。

现在已知无论什么时候，“模式串中一定含有s1”（因为前面的字符一定都是匹配成功才能使指针指向当前位置），而s2为s1的后缀，那么模式串中就一定含有s2。如果s2是个独立的单词，那么就累加上它的贡献。

同理，现在已知模式串中也含有s2，那么就将s2当做新的s1，重复以上过程。通过不断跳fail数组直到跳到根节点，将所有贡献累加上。

int count()
{
	int len=s.size(),k=0,ans=0;
	for(int i=0;i<len;i++)
	{
		k=trie[k].nx[s[i]-'a'];
		//无论有无这个儿子都向后跳。因为如果没有，相当于回根节点重新匹配 
		int t=k;
		while(t)
		{
			ans+=trie[t].end;//先累加贡献。因为当前节点的贡献也要累加 
			trie[t].end=0;//赋值为0，避免重复统计(当然，还有赋值为-1的写法) 
			t=fail[t];//向前跳 
		}
	}
	return ans;
}