Pagini recente » Cod sursa (job #2260644) | Cod sursa (job #942468) | Cod sursa (job #2050367) | Cod sursa (job #2359928) | Cod sursa (job #498330)
Cod sursa(job #498330)
#include <stdio.h>
#include <string.h>
struct hash
{
long nod;
hash *link;
}*H[100010];
long nr,n,m,i,sol1,sol2,M1,M2,pow1,pow2;
hash *p;
char string[10000010],s[25];
int main()
{
freopen("abc2.in","r",stdin);
freopen("abc2.out","w",stdout);
fgets(string,10000010,stdin);
n=strlen(string)-1;
if(string[n]=='\n') n--;
fgets(s,25,stdin);
m=strlen(s)-1;
if(s[m]=='\n') m--;
sol1=0;
sol2=0;
M1=100007;
M2=100021;
for(i=0;i<=m;i++)
{
sol1=(sol1*3+s[i])%M1;
sol2=(sol2*3+s[i])%M2;
}
p=new hash;
p->nod=sol2;
p->link=H[sol1];
H[sol1]=p;
while(!feof(stdin))
{
fgets(s,25,stdin);
sol1=0;
sol2=0;
for(i=0;i<=m;i++)
{
sol1=(sol1*3+s[i])%M1;
sol2=(sol2*3+s[i])%M2;
}
p=new hash;
p->nod=sol2;
p->link=H[sol1];
H[sol1]=p;
}
nr=0;
sol1=0;
sol2=0;
for(i=0;i<=m;i++)
{
sol1=(sol1*3+string[i])%M1;
sol2=(sol2*3+string[i])%M2;
}
pow1=1;
pow2=1;
for(i=1;i<=m;i++)
{
pow1=(pow1*3)%M1;
pow2=(pow2*3)%M2;
}
p=H[sol1];
while(p!=NULL)
{
if(p->nod==sol2)
{
nr++;
break;
}
p=p->link;
}
for(i=m+1;i<=n;i++)
{
sol1=((sol1+M1-(pow1*string[i-m-1])%M1)*3+string[i])%M1;
sol2=((sol2+M2-(pow2*string[i-m-1])%M2)*3+string[i])%M2;
p=H[sol1];
while(p!=NULL)
{
if(p->nod==sol2)
{
nr++;
break;
}
p=p->link;
}
}
printf("%ld\n",nr);
return 0;
}