HDUOJ 2222 Keywords Search（AC自动机）

solution：AC自动机的经典例题，都不需要改什么，直接套模板就可以了

#include <bits/stdc++.h>
using namespace std;

struct node{
	node* next[26];
	node* fail;
	int cnt;
	node(){
		for (int i = 0; i <26; ++i)next[i] = NULL;
		cnt = 0;
		fail = NULL;
	}
}*q[500010];

node *root;
int head, tail;
char str[1000005];

void insert(char *str)
{
	node *p = root;
	int i = 0, index;
	while (str[i]){
		index = str[i] - 'a';
		if (p->next[index] == NULL)p->next[index] = new node();
		p = p->next[index];
		++i;
	}
	++p->cnt;
}

void build(node* root)
{
	root->fail = NULL;
	q[tail++] = root;
	while (head < tail){
		node* temp = q[head++];
		node* p = NULL;
		for (int i = 0; i < 26; ++i){
			if (temp->next[i] != NULL){
				if (temp == root)temp->next[i]->fail = root;
				else{
					p = temp->fail;
					while (p != NULL){
						if (p->next[i] != NULL){
							temp->next[i]->fail = p->next[i];
							break;
						}
						p = p->fail;
					}
					if (p == NULL)temp->next[i]->fail = root;
				}
				q[tail++] = temp->next[i];
			}
		}
	}
}

int query(node *root)
{
	int i = 0, cnt = 0, index;
	node* p = root;
	while (str[i]){
		index = str[i] - 'a';
		while (p->next[index] == NULL && p != root)p = p->fail;
		p = p->next[index];
		if (p == NULL)p = root;
		node* temp = p;
		while (temp != root && temp->cnt != -1){
			cnt += temp->cnt;
			temp->cnt = -1;
			temp = temp->fail;
		}
		++i;
	}
	return cnt;
}

int main()
{
	int t, n;
	scanf("%d", &t);
	while (t--){
		head = tail = 0;
		root = new node();
		scanf("%d", &n);
		while(n--){
			scanf("%s", str);
			insert(str);
		}
		build(root);
		scanf("%s", str);
		printf("%d\n", query(root));
	}
	return 0;
}