HDU 2222 AC自动机模版题

所学的AC自动机都源于斌哥和昀神的想法。

题意：求目标串中出现了几个模式串。

使用一个int型的end数组记录，查询一次。

#include <cstdio>

#include <cstring>

#include <queue>

using namespace std;

const int maxw = 50 * 10000 + 10;

const int sigma_size = 26;

const int maxl = 1000000 + 10;

struct Trie{

	int next[maxw][sigma_size],fail[maxw],end[maxw];

	int root,L;

	int newnode(){

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

		    next[L][i]=-1;

		end[L++]=0;

		return L-1;

	}

	void init(){

		L=0;

		root=newnode();

	}

	void insert(const char *buf){

		int now=root,len=strlen(buf);

		for(int i=0;i<len;i++){

			if(next[now][buf[i]-'a']==-1)

			    next[now][buf[i]-'a']=newnode();

			now=next[now][buf[i]-'a'];

		}

		end[now]++;

	}

	void build()

	{

		queue<int>Q;

		fail[root]=root;

		for(int i=0;i<sigma_size;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<sigma_size;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 query(const char *buf){

	    int now=root,len=strlen(buf);

		int res=0;

		for(int i=0;i<len;i++){

			now=next[now][buf[i]-'a'];

			int tmp=now;

			while(tmp!=root){

				res+=end[tmp];

				end[tmp]=0;

				tmp=fail[tmp];

			}

		}

		return res;

	}

};

Trie ac;

char buf[maxl];

int main()

{

	int T,n;

	scanf("%d",&T);

	while(T--)

	{

		scanf("%d",&n);

		ac.init();

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

		{

			scanf("%s",buf);

			ac.insert(buf);

		}

		ac.build();

		scanf("%s",buf);

		int ans=ac.query(buf);

		printf("%d\n",ans);

	}

	return 0;

}

巴特西

HDU 2222 AC自动机模版题

最新文章

热门文章