AC自动机

代码

#include 
#include 

using namespace std;

const int maxn = 26;

struct node{ // 字典树节点 
	int cnt;
	node *fail; // 失配指针 
	node *next[maxn];	
}*que[500005]; // 队列 

node *createNode(){ // 创建一个新的字典树节点 
	node *p = new node();
	p->cnt = 0;
	p->fail = NULL;
	for(int i = 0; i < maxn; i++)
		p->next[i] = NULL;
	return p;
}

void insertStr(node *root, string str){ // 建立一棵字典树 
	node *p;
	if(root == NULL){
		p = createNode();
		root = p;
	}
	p = root;
	for(int i = 0; i next[k] == NULL)
			p->next[k] = createNode();
		p = p->next[k];
	}
	p->cnt++;
}

void buildFailTree(node *root){ // 建立失配指针关系 
	int head = 0;
	int tail = 0;
	que[head++] = root;
	while(head != tail){
		node *p = NULL;
		node *tmp = que[tail++];
		for(int i = 0; i < 26; i++){
			if(tmp->next[i] != NULL){
				if(tmp->next[i] == root)
					tmp->next[i]->fail = root;
				else{
					p = tmp->fail;
					while(p != NULL){
						if(p->next[i] != NULL){
							tmp->next[i]->fail = p->next[i];
							break;
						}
						p = p->fail;
					}
					if(p == NULL)
						tmp->next[i]->fail = root;
				}
				que[head++] = tmp->next[i];
			}
		}
	}
}

int queryStr(node *root, string str){ // 查询 
	node *p = root;
	int ans = 0;
	for(int i = 0; i < str.length(); i++){
		int k = str[i] - 'a';
		while(p->next[k] == NULL && p != root)
			p = p->fail;
		p = p->next[k];
		if(p == NULL)
			p = root;
		node *tmp = p;
		while(tmp != root){
			if(tmp->cnt >= 0){
				ans += tmp->cnt;
				tmp->cnt = -1;
			}
			else
				break;
			tmp = tmp->fail;
		}
	}
	return ans;
}

int main(){
	node *root = createNode();
	int n;
	cin >> n;
	for(int i = 0; i < n; i++){
		string str;
		cin >> str;
		insertStr(root, str);
	}
	buildFailTree(root);
	while(1){
		string str;
		cin >> str;
		cout << queryStr(root, str) << endl;;
	}
}