Pagini recente » Cod sursa (job #2124813) | Cod sursa (job #234658) | Cod sursa (job #2551811) | Cod sursa (job #826771) | Cod sursa (job #1085731)
/*
~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]);
}