Keywords Search

1
5
she
he
say
shr
her
yasherhs

3

ac自动机模板题

代码：

/* ***********************************************
Author :xianxingwuguan
Created Time :2014-2-2 16:23:08
File Name :2.cpp
************************************************ */
#pragma comment(linker, "/STACK:102400000,102400000")
#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <sstream>
#include <stdlib.h>
#include <string.h>
#include <limits.h>
#include <string>
#include <time.h>
#include <math.h>
#include <queue>
#include <stack>
#include <set>
#include <map>
using namespace std;
#define INF 0x3f3f3f3f
#define eps 1e-8
#define pi acos(-1.0)
typedef long long ll;
struct Trie {
	int next[600100][26],fail[600020],L,end[600100],root;
	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 *str){
		int len=strlen(str);
		int now=root;
		for(int i=0;i<len;i++){
			if(next[now][str[i]-‘a‘]==-1)
				next[now][str[i]-‘a‘]=newnode();
			now=next[now][str[i]-‘a‘];
		}
		end[now]++;
	}
	void build(){
		queue<int> q;
		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)
					next[now][i]=next[fail[now]][i];
				else {
					fail[next[now][i]]=next[fail[now]][i];
					q.push(next[now][i]);
				}
		}
	}
	int solve(char *str){
		int len=strlen(str);
		int now=root;
		int res=0;
		for(int i=0;i<len;i++){
			now=next[now][str[i]-‘a‘];
			int temp=now;
			while(temp!=root&&end[temp]!=-1){
				res+=end[temp];
				end[temp]=-1;
				temp=fail[temp];
			}
		}
		return res;
	}
}ac;
char str[1000100];
int main()
{
     //freopen("in.txt","r",stdin);
     //freopen("out.txt","w",stdout);
      int T;
	  scanf("%d",&T);
	  while(T--){
		  int n;
		  scanf("%d",&n);
		  ac.init();
		  while(n--){
              scanf("%s",str);
			  ac.insert(str);
		  }
		  ac.build();
		  scanf("%s",str);
		  printf("%d\n",ac.solve(str));
	  }
     return 0;
}
/*
5 she he say shr her yasherhshersher

*/

hdu 2222 ac自动机 模式串计数

原文：http://blog.csdn.net/xianxingwuguan1/article/details/18900187