Cod sursa(job #1149869)

Utilizator vladrochianVlad Rochian vladrochian Data 22 martie 2014 12:54:19
Problema Aho-Corasick Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.45 kb
#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;
class trie
{
	public:
	vector<int> nd;
	int n0;
	trie *fiu[26],*fail;
	trie()
	{
		n0=0;
		fail=0;
		memset(fiu,0,sizeof fiu);
	}
	void ins(char *l,int id)
	{
		if(!*l)
		{
			nd.push_back(id);
			return;
		}
		int lit=*l-'a';
		if(!fiu[lit])
			fiu[lit]=new trie;
		fiu[lit]->ins(l+1,id);
	}
}*t=new trie,*q[10002];
int n,sol[100],qe;
char txt[1000002],cuv[10002];
void bfs()
{
	t->fail=t;
	q[++qe]=t;
	for(int i=1;i<=qe;++i)
	{
		trie *crt=q[i];
		for(int j=0;j<26;++j)
			if(crt->fiu[j])
			{
				trie *fl=crt->fail;
				while(fl!=t && !fl->fiu[j])
					fl=fl->fail;
				if(fl->fiu[j] && fl->fiu[j]!=crt->fiu[j])
					fl=fl->fiu[j];
				crt->fiu[j]->fail=fl;
				q[++qe]=crt->fiu[j];
			}
	}
	t->fail=0;
}
void kmp()
{
	trie *p=t;
	for(int i=0;txt[i];++i)
	{
		int lit=txt[i]-'a';
		while(!p->fiu[lit] && p!=t)
			p=p->fail;
		if(p->fiu[lit])
			p=p->fiu[lit];
		++(p->n0);
	}
}
void antibfs()
{
	while(qe)
	{
		trie *crt=q[qe--];
		if(crt->fail)
			crt->fail->n0+=crt->n0;
		for(size_t j=0;j<crt->nd.size();++j)
			sol[crt->nd[j]]=crt->n0;
	}
}
int main()
{
	int i;
	freopen("ahocorasick.in","r",stdin);
	freopen("ahocorasick.out","w",stdout);
	scanf("%s%d",txt,&n);
	for(i=0;i<n;++i)
	{
		scanf("%s",cuv);
		t->ins(cuv,i);
	}
	bfs();
	kmp();
	antibfs();
	for(i=0;i<n;++i)
		printf("%d\n",sol[i]);
	return 0;
}