AC自动机模版

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

void insert(char *s)
{
	int n = strlen(s);
	node *curr = root;
	for(int i = 0; i < n; i++)
	{
		int c = s[i] - ‘a‘;
		if(curr->next[c] == NULL)
		{
			node *newnode = new node;
			curr->next[c] = newnode;
		}
		curr = curr->next[c];
		
	}
	curr->val++;
}

void build()
{
	root->fail = NULL;
	queue <node*> Q;
	Q.push(root);
	while(!Q.empty())
	{
		
		node *temp = Q.front();
		node *p = NULL;
		Q.pop();
		for(int i = 0; i < 26; i++)
		{
			if(temp->next[i] == NULL)
				continue;
			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.push(temp->next[i]);
		}
	}
}
void find(char *s)
{
	int n = strlen(s);
	node *p = root;
	for(int i = 0; i < n; i++)
	{
		int c = s[i] - ‘a‘;
		while(p != root && p->next[c] == NULL)
			p = p->fail;
		p = p->next[c];
		if(p == NULL)
			p = root;
		node *temp = p;
		while(temp != root)
		{
			ans += temp->val;
			temp->val = 0;
			temp = temp->fail;
		}
	}
}

void del(node *p)
{
	for(int i = 0; i < 26; i++)
	{
		if(p->next[i] != NULL)
			del(p->next[i]);
	}
	free(p);
}

AC自动机模版,布布扣,bubuko.com

AC自动机模版

原文：http://blog.csdn.net/u011686226/article/details/23664813