Pagini recente » Cod sursa (job #1691511) | Cod sursa (job #686760) | Cod sursa (job #1373101) | Cod sursa (job #380368) | Cod sursa (job #498359)
Cod sursa(job #498359)
#include <stdio.h>
#include <string.h>
unsigned int m,n,i,pos,sol,pow1,nr,M,pow2;
char string[10000010],s[25];
struct hash
{
unsigned int nod;
hash *link;
}*H[700000];
inline void add(unsigned int pos,unsigned int sol)
{
hash *p;
p=new hash;
p->nod=sol;
p->link=H[pos];
H[pos]=p;
}
inline int find(unsigned int pos,unsigned int sol)
{
hash *p;
p=H[pos];
while(p!=NULL)
{
if(p->nod==sol) return 1;
p=p->link;
}
return 0;
}
int main()
{
freopen("abc2.in","r",stdin);
freopen("abc2.out","w",stdout);
fgets(string,10000010,stdin);
n=strlen(string)-2;
M=666013;
fgets(s,25,stdin);
m=strlen(s)-2;
pos=0;
sol=0;
for(i=0;i<=m;i++)
{
pos=(pos*4+s[i]-'a')%M;
sol=sol*4+s[i]-'a';
}
add(pos,sol);
while(!feof(stdin))
{
fgets(s,25,stdin);
pos=0;
sol=0;
for(i=0;i<=m;i++)
{
pos=(pos*4+s[i]-'a')%M;
sol=sol*4+s[i]-'a';
}
add(pos,sol);
}
pos=0;
sol=0;
for(i=0;i<=m;i++)
{
pos=(pos*4+string[i]-'a')%M;
sol=sol*4+string[i]-'a';
}
add(pos,sol);
pow1=1;
pow2=1;
for(i=1;i<=m;i++)
{
pow1*=4;
pow1%=M;
pow2*=4;
}
nr=0;
if(find(pos,sol)) nr++;
for(i=m+1;i<=n;i++)
{
pos=((pos+M-pow1*(string[i-m-1]-'a'))*4+string[i]-'a')%M;
sol=(sol-pow2*(string[i-m-1]-'a'))*4+string[i]-'a';
if(find(pos,sol)) nr++;
}
printf("%d\n",nr);
return 0;
}