hdu 2222 Keywords_ac自动机模板

题意：给你n个单词，再给你一串字符，求在字符中有多少个单词出现过

#include <iostream>

#include<cstdio>

#include<cstring>

using namespace std;

#define N 10010

#define MAXLEN 1000010

struct node{

	node *child[26];

	node *fail;

	int count;

	void init(){

		for(int i=0;i<26;i++)

			child[i]=NULL;

		count=0;

		fail=NULL;

	}

}*q[50*N];

node *root;

int head,tail;

void insert(char *str){//构建前缀树

	node *now,*next;

	int i=0,t;

	now=root;

	while(str[i]){

		t=str[i]-'a';

		if(now->child[t]!=NULL)

			now=now->child[t];

		else{

			next=new node;

			next->init();

			now->child[t]=next;

			now=next;

		}

		i++;

	}

	now->count++;

}

void build_fail(){

	int i;

	node *now,*p;

	head=tail=0;

	now=root;

	q[tail++]=now;

	while(head<tail){

		now=q[head];

		for(i=0;i<26;i++){

			if(now->child[i]==NULL) continue;

			if(now==root) now->child[i]->fail=root;

			else{

				p=now->fail;

				while(p!=NULL){

					if(p->child[i]!=NULL){

						now->child[i]->fail=p->child[i];

						break;

					}

					p=p->fail;

				}

				if(p==NULL) now->child[i]->fail=root;

			}

			q[tail++]=now->child[i];

		}

		head++;

	}

}

int query(char *str){

	node *now,*temp;

	int i,t,cnt;

	i=cnt=0;

	now=root;

	while(str[i]){

		t=str[i]-'a';

		while(now->child[t]==NULL&&now!=root) now=now->fail;

		now=now->child[t];

		if(now==NULL) now=root;

		temp=now;

		while(temp!=NULL&&temp->count!=-1){

			cnt+=temp->count;

			temp->count=-1;

			temp=temp->fail;

		}

		i++;

	}

	return cnt;

}

int main(int argc, char** argv) {

	int t,n;

	char str[MAXLEN];

	scanf("%d",&t);

	while(t--){

		scanf("%d",&n);

		root=new node;

		root->init();

		while(n--){

			scanf("%s",str);

			insert(str);

		}

		build_fail();

		scanf("%s",str);

		printf("%d\n",query(str));

	}

	return 0;

}

巴特西

hdu 2222 Keywords_ac自动机模板

最新文章

热门文章