Pagini recente » Cod sursa (job #777550) | Cod sursa (job #26974) | Cod sursa (job #385929) | Cod sursa (job #255743) | Cod sursa (job #2440285)
#include <iostream>
#include <fstream>
#include <queue>
#include <list>
#include <vector>
using namespace std;
struct nod
{
int cnt;
vector<int> id;
nod* back;
nod* son['z'-'a'+1]={0};
};
char c[1005000];
char v[150][10500];
int countt[150];
nod * root;
int n,t;
nod * q[10500*150];
void insert( char * p, nod * nd, int i)
{
if((*p)=='\0')
{
nd->id.push_back(i);
return;
}
if(nd->son[(*p)-'a']==0)
nd->son[(*p)-'a']= new nod;
insert(p+1,nd->son[(*p)-'a'],i);
}
int main()
{
freopen("ahocorasick.in","r",stdin);
freopen("ahocorasick.out","w",stdout);
scanf("%s",c);
scanf("%d",&n);
root= new nod;
root->back= root;
for(int i=0;i<n;i++)
{
scanf("%s",v[i]);
insert(v[i],root,i);
}
/* q[0]=root;
for(int i=0;i<=t;++i)
{
nod * tp= q[i];
for(int i=0;i<='z'-'a';i++)
{
nod * u = tp->son[i];
if(u!=0)
{
nod *nd= tp->back;
while( nd!=root &&nd->son[i]==0)
nd= nd->back;
if(nd->son[i]!=0 && nd->son[i]!=u)
nd=nd->son[i];
u->back= nd;
t++;
q[t]=u;
}
}
}
root->back=0;
nod *nd= root;
for(int i=0;c[i]!='\0';i++)
{
int ch = c[i]-'a';
while(nd->son[ch]==0 && nd!=root) nd= nd->back;
if(nd->son[ch]!=0)
nd=nd->son[ch];
(nd->cnt)++;
}
for(int i=t;i>0;i--)
{
nod * u =q[i];
for(int it= 0;it!=u->id.size();++it )
countt[u->id[it]]+=u->cnt;
u->back->cnt+=u->cnt;
}*/
for(int i=0;i<n;i++)
printf("%d\n",countt[i]);
}