Cod sursa(job #1085731)

Utilizator roby2001Sirius roby2001 Data 17 ianuarie 2014 12:21:56
Problema Aho-Corasick Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.07 kb
/*
          ~Keep It Simple!~
*/
  
#include <stdio.h>
#include <string.h>
#include <vector>

using namespace std;

#define NmaX 1000005

char P[NmaX];
int N,prim,ultim,fina[10005];

struct T
{
	vector<int> Words;
	T* next[30];
	T* fail;
	int nr;

	T()
	{
		fail = 0;
		nr = 0;
		memset(next,0,sizeof(next));
	}
};

T *Trie = new T();
T *Q[10005 * 10005];

void AddToTrie(char* x, T* node, int nrc)
{
	if( x[0] == 0 )
	{
		node->Words.push_back(nrc);
		return;
	}
	else
	{
		if( !node->next[x[0]-'a'] )
			node->next[x[0]-'a'] = new T();;
		AddToTrie(x+1,node->next[x[0]-'a'],nrc);
	}
}

void BFS()
{
	T *aux;

    prim = ultim = 1;
	Q[prim] = Trie;
	Trie->fail = Trie;

	while(prim <= ultim)
	{
		for(int i=0; i<='z'-'a'; i++)
			if( Q[prim]->next[i] )
			{
				for( aux = Q[prim] -> fail; aux!=Trie && !aux->next[i]; aux = aux->fail);

				if( aux -> next[i] && aux->next[i] != Q[prim]->next[i] ) aux = aux->next[i];
				Q[prim]->next[i]->fail = aux;
				Q[++ultim] = Q[prim]->next[i];
			}
		prim++;
	}

	//Trie->fail = NULL;
}

void CalculateMatches()
{
	int textsize = strlen(P);
	T* R = Trie;
/*	for(int i=0; i<textsize; i++)
	{
		int j = P[i] - 'a';

		if(R->next[j])
		{
			R = R->next[j];
			R->nr++;
		}
		else
		{
			while( R!=Trie && R->next[j] == 0 ) R = R->fail;
			if(R->next[j])
			   R=R->next[j];
			R -> nr ++;
		}
		//   R->fail->nr++;
	}*/

	for(int i=0; i<textsize; i++)
	{
		int j = P[i] - 'a';
		while( R!=Trie && R->next[j] == 0 ) R = R->fail;
			if(R->next[j])
			   R=R->next[j];
			R -> nr ++;
	}

	for(int i=ultim; i>0; i--)
	{
		if( Q[i]->fail )
			Q[i]->fail->nr += Q[i]->nr;
		for( int z = 0; z<Q[i]->Words.size(); z++) 
			fina[Q[i]->Words[z]] = Q[i]->nr;
	}
}

int main()
{
	freopen("ahocorasick.in","r",stdin);
	freopen("ahocorasick.out","w",stdout);

	scanf("%s %d",P,&N);

	char c[10005];

	for(int i=1; i<=N; i++)
	{
		scanf("%s",c);
		AddToTrie(c,Trie,i);
	}

	BFS();

	CalculateMatches();

	for(int i=1; i<=N; i++)
		printf("%d\n",fina[i]);
}