hdu2222 Keywords Search【AC自动机】

题意：

t组数据，每次给你n个模式串，和一个长串，请问这个长串里面包含几个模式串
n的范围为1e4,每个模式串的长度不超过50，长串的长度不超过1e6

题解：

AC自动机入门，也是我第一次写AC自动机
学习博客
模板用的是kuangbin的模板

要点：
fail数组初始化都为0，而我的trie的根节点也为0
套路总结:
先初始化空的自动机，插入每个模式串，建立字典树，对建立完的字典树跑一遍bfs建立fail指针

AC_code：

#include<bits/stdc++.h>
using namespace std;
const int maxn = 5e5+5;
struct tree {
	int next[maxn][26], fail[maxn], end[maxn];
	int root, L;
	int newnode() {
		for(int i = 0; i < 26; i++) {
			next[L][i] = -1;
		}
		end[L++] = 0;
		return L-1;
	}
	void init() {
		L = 0;
		root = newnode();
	}
	void insert(char buf[]) {
		int len = strlen(buf);
		int now = root;
		for(int i = 0; i < len; i++) {
			if(next[now][buf[i]-'a'] == -1) {
				next[now][buf[i]-'a'] = newnode();
			}
			now = next[now][buf[i]-'a'];
		}
		end[now]++;
	}

	void build() { //使用bfs 建立fail指针
		queue<int> Q;
// cout<<root<<endl;
		fail[root] = root;
		for(int i = 0; i < 26; i++) {
			if(next[root][i] == -1) {
				next[root][i] = root;
			} else {
				fail[next[root][i]] = root;
				Q.push(next[root][i]);
			}
		}
		while(!Q.empty()) {
			int now = Q.front();
			Q.pop();
			for(int i = 0; i < 26; i++) {
				if(next[now][i] == -1) {
// cout<<now<<" "<<fail[now]<<endl;
					next[now][i] = next[fail[now]][i];
				} else {
// cout<<now<<" "<<next[now][i]<<" "<<fail[next[now][i]]<<endl; 
					fail[next[now][i]] = next[fail[now]][i];
					Q.push(next[now][i]);
				}
			}
		}
	}
	int query(char buf[]) {
		int len = strlen(buf);
		int now = root;
		int res = 0;
		for(int i = 0; i < len; i++) {
			now = next[now][buf[i]-'a'];
			int temp = now;
			while(temp != root) {
				res += end[temp];
				end[temp] = 0;
				temp = fail[temp];
			}
		}
		return res;
	}
};
tree ac;
char buf[maxn*2];
int main() {
	int t, n;
	scanf("%d", &t);
	while(t--) {
		scanf("%d", &n);
		ac.init();
		for(int i = 0; i < n; i++) {
			scanf("%s", buf);
			ac.insert(buf);
		}
		ac.build();
		scanf("%s", buf);
		int ans = ac.query(buf);
		printf("%d\n", ans);
	}
}