AC自动机

魔板

• 思想:
  相当于在trie树上的KMP。
• 流程:
  1.构建trie树
  注意0为根会方便很多。
  2.get_fail()
  虽然和KMP很相似，我举一反三的能力有限，所以还是要重新讲qwq
  fail[i]：表示满足i为结尾的后缀与rt开始的前缀匹配的最大长度。
  求法为了无后效性，用BFS（按层遍历），每次枚举相邻的trie树继续匹配下去，匹配不明显，但是很短，巧妙地运用了fail和trie的性质。
  3.文本串在trie树上浪
  从跟开始，记录u指针，逐步往下，每跳一步，不能局限于当前的格局，还要一直迭代到fail=0为止，当然原指针为止不变。
  你会发现如果u走不下去了，就会自动为0，到根节点【1明白了吧】，重新匹配。
  当然不用想这么多，AC制动机是个DFN，只要暴力往下走就行了。
• 代码：

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+5;
int go[N][27],fail[N],cnt[N],tcnt=0;
char s[N];
void Insert() {
	int sz=strlen(s),u=0;
	for(int i=0;i<sz;i++) {
		int x=s[i]-‘a‘;
		if(!go[u][x]) go[u][x]=++tcnt;
		u=go[u][x];
	}
	cnt[u]=1;
}
void get_fail() {
	queue<int> Q;
	for(int i=0;i<26;i++) if(go[0][i])fail[go[0][i]]=0,Q.push(go[0][i]);
	while(!Q.empty()) {
		int u=Q.front(); Q.pop();
		for(int i=0;i<26;i++) {
			if(go[u][i]) fail[go[u][i]]=go[fail[u]][i],Q.push(go[u][i]);
			else go[u][i]=go[fail[u]][i];
		}
	}
}
int Query() {
	int sz=strlen(s),u=0,ans=0;
	for(int i=0;i<sz;i++) {
		u=go[u][s[i]-‘a‘];
		for(int j=u;j&&cnt[j]!=-1;j=fail[j]) {
			ans+=cnt[j],cnt[j]=-1;
		}
	}
	return ans;
}
int main() {
	int n;
	scanf("%d",&n);
	for(int i=1;i<=n;i++) {
		scanf("%s",s);
		Insert();
	}
	get_fail();
	scanf("%s",s);
	printf("%d",Query());
	return 0;
}

AC自动机

原文：https://www.cnblogs.com/bestime/p/15050863.html