Pagini recente » Cod sursa (job #708178) | Cod sursa (job #2445758) | Cod sursa (job #204422) | Cod sursa (job #2489475) | Cod sursa (job #2314600)
#include<stdio.h>
#include<vector>
#include<string.h>
using namespace std;
struct node
{
int occ;
node *next[30];
node *back_step;
node()
{
occ=0;
for(int i=0;i<28;++i)next[i]=NULL;
}
};
char text[1000005],words[105][10005];
int n;
node *trie;
vector<node*>Q;
node* add_word(node* current_n,char *word,int ind)
{
if(!current_n)current_n=new node;
if(word[ind]=='\0')return current_n;
current_n->next[word[ind]-'a']=add_word(current_n->next[word[ind]-'a'],word,ind+1);
return current_n;
}
int get_occ(node* current_n,char *word,int ind)
{
if(word[ind]=='\0')return current_n->occ;
return get_occ(current_n->next[word[ind]-'a'],word,ind+1);
}
void create_aho()
{
trie->back_step = trie;
Q.push_back(trie);
int ind=0;
while(ind<Q.size())
{
for(int i=0;i<='z'-'a';++i)
{
node* next_n=Q[ind]->next[i];
if(next_n)
{
Q.push_back(next_n);
node *back=Q[ind]->back_step;
while(back!=trie&&back->next[i]==NULL)back=back->back_step;
if(back->next[i]!=NULL&&back->next[i]!=next_n)next_n->back_step=back->next[i];
else next_n->back_step=trie;
}
}
ind++;
}
}
int main()
{
freopen("ahocorasick.in","r",stdin);
freopen("ahocorasick.out","w",stdout);
gets(text);
scanf("%d\n",&n);
for(int i=0;i<n;++i)
{
gets(words[i]);
trie = add_word(trie,words[i],0);
}
create_aho();
int l=strlen(text);
node *current_n=trie;
for(int i=0;i<l;++i)
{
while(current_n!=trie&¤t_n->next[text[i]-'a']==NULL)current_n=current_n->back_step;
if(current_n->next[text[i]-'a']!=NULL)current_n=current_n->next[text[i]-'a'];
current_n->occ++;
}
for(int i=Q.size()-1;i>=0;--i)
Q[i]->back_step->occ+=Q[i]->occ;
for(int i=0;i<n;++i)printf("%d\n",get_occ(trie,words[i],0));
return 0;
}