Pagini recente » Cod sursa (job #3130251) | Cod sursa (job #1340219) | Cod sursa (job #1886534) | Cod sursa (job #1073603) | Cod sursa (job #1225698)
#include<cstdio>
#include<vector>
#include<queue>
using namespace std;
char s[1000001];
int rez[101];
class Ahocorasick
{
public:
struct Nod
{
Nod *advance[26],*euro,*dolar;
int ind;
Nod()
{
int i;
for(i=0;i<=25;i++)
advance[i]=0;
euro=0;
dolar=0;
ind=0;
}
};
Nod *alpha;
Ahocorasick()
{
alpha=new Nod;
}
void add(char *s,int ind)
{
int i;
Nod *poz;
poz=alpha;
for(i=0;s[i];i++)
{
if(poz->advance[s[i]-'a']==0)
poz->advance[s[i]-'a']=new Nod;
poz=poz->advance[s[i]-'a'];
}
poz->ind=ind;
}
void dolar_euro()
{
queue <Nod*> q;
int i;
Nod *tata,*temp;
alpha->dolar=0;
alpha->euro=alpha;
for(i=0;i<26;i++)
if(alpha->advance[i]!=NULL)
{
alpha->advance[i]->dolar=alpha;
q.push(alpha->advance[i]);
}
while(!q.empty())
{
tata=q.front();
q.pop();
for(i=0;i<26;i++)
if(tata->advance[i]!=NULL)
{
temp=tata;
while(temp->dolar!=NULL&&temp->dolar->advance[i]==NULL)
temp=temp->dolar;
if(temp==NULL)
tata->advance[i]->dolar=alpha;
else
tata->advance[i]->dolar=temp->dolar->advance[i];
q.push(tata->advance[i]);
}
if(tata->dolar->ind!=0)
tata->euro=tata->dolar;
else
tata->euro=tata->dolar->euro;
}
}
};
Ahocorasick A;
int main()
{
int n,i;
char temp[10001];
freopen("ahocorasick.in","r",stdin);
freopen("ahocorasick.out","w",stdout);
gets(s);
scanf("%d\n",&n);
for(i=1;i<=n;i++)
{
gets(temp);
A.add(temp,i);
}
A.dolar_euro();
Ahocorasick::Nod *poz,*euro;
poz=A.alpha;
for(i=0;s[i]!=0;i++)
{
while(poz->dolar!=NULL&&poz->advance[s[i]-'a']==NULL)
{
poz=poz->dolar;
}
if (poz->advance[s[i]-'a']!=NULL)
poz=poz->advance[s[i]-'a'];
if(poz->ind!=0)
{
rez[poz->ind]++;
}
euro=poz->euro;
while(euro!=A.alpha)
{
rez[euro->ind]++;
euro=euro->euro;
}
}
for(i=1;i<=n;i++)
{
printf("%d\n",rez[i]);
}
return 0;
}