Pagini recente » Cod sursa (job #1261129) | Cod sursa (job #2806968) | Cod sursa (job #2024001) | Cod sursa (job #2081649) | Cod sursa (job #1225712)
#include<cstdio>
#include<vector>
#include<queue>
#include<cstring>
using namespace std;
char s[1000001],m[101][10001];
int rez[101],r[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->dolar==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,nn,cnt,j;
char temp[10001];
freopen("ahocorasick.in","r",stdin);
freopen("ahocorasick.out","w",stdout);
gets(s);
scanf("%d\n",&n);
nn=0;
for(i=1;i<=n;i++)
{
gets(temp);
cnt=1;
for(j=1;j<=nn;j++)
if(strcmp(m[j],temp)==0)
{
cnt=0;
r[i]=j;
break;
}
if(cnt==1)
{
strcpy(m[++nn],temp);
r[i]=nn;
A.add(temp,nn);
}
}
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[r[i]]);
}
return 0;
}