AC自动机模板

其实AC自动机就是KMP与trie的结合体。

模板与KMP很像（其实就是把线性拓展改为BFS拓展）。

这里的模板是给出若干个单词，在给出一个长度很大的串，求串中出现了多少个给出的单词。

#include
using namespace std;
char s[1010000];
int trie[5010000][30],tot=0;
int cnt[5010000];
int n;
void insert(char *ch){
	int p=0;
	int len=strlen(ch);
	for(int i=0;i q;
void ACbuild(){
	for(int i=0;i<26;i++) if(trie[0][i]) q.push(trie[0][i]);
	while(!q.empty()){
		int t=q.front();q.pop();
		for(int i=0;i<26;i++){
			int c=trie[t][i];
			if(!c) continue;
			int j=nxt[t];
			while(j&&!trie[j][i]) j=nxt[j];
			if(trie[j][i]) j=trie[j][i];
			nxt[c]=j;
			q.push(c);
		}
	}
}
int main(){
	scanf("%d",&n);
	while(n--){
		scanf("%s",s);
		insert(s);
	}
	ACbuild();
	scanf("%s",s);
	int ans=0;
	int len=strlen(s);
	for(int i=0,j=0;i 
使用例：