Pagini recente » Cod sursa (job #3257380) | Cod sursa (job #1600806) | Cod sursa (job #330454) | Cod sursa (job #479477) | Cod sursa (job #497603)
Cod sursa(job #497603)
#include <stdio.h>
#include <string.h>
struct hash
{
int nod1,nod2;
hash *link;
}*H[100100];
int nr,n,m,i,sol1,sol2,M1,M2,pw,sol;
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=100021;
M2=1003;
for(i=0;i<=m;i++)
{
sol1=(sol1*3+s[i])%M1;
sol2+=s[i];
}
p=new hash;
p->nod1=sol1;
p->nod2=sol;
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+=s[i];
}
p=new hash;
p->nod1=sol1;
p->nod2=sol;
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+=string[i];
}
pw=1;
for(i=1;i<=m;i++)
pw=(pw*3)%M1;
p=H[sol1];
while(p!=NULL)
{
if(p->nod1==sol1&&p->nod2==sol)
{
nr++;
break;
}
p=p->link;
}
for(i=m+1;i<=n;i++)
{
sol1=((sol1+M1-(pw*string[i-m-1])%M1)*3+string[i])%M1;
sol2=sol2-string[i-m-1]+string[i];
p=H[sol1];
while(p!=NULL)
{
if(p->nod1==sol1&&p->nod2==sol)
{
nr++;
break;
}
p=p->link;
}
}
printf("%d\n",nr);
return 0;
}