Pagini recente » Cod sursa (job #1910878) | Cod sursa (job #1169993) | Cod sursa (job #1992970) | Cod sursa (job #2229552) | Cod sursa (job #497607)
Cod sursa(job #497607)
#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;
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=10000007;
for(i=0;i<=m;i++)
{
sol1=(sol1*3+s[i])%M1;
sol2=(sol2+s[i])%M2;
}
p=new hash;
p->nod1=sol1;
p->nod2=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+s[i])%M2;
}
p=new hash;
p->nod1=sol1;
p->nod2=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+string[i])%M2;
}
pw=1;
for(i=1;i<=m;i++)
pw=(pw*3)%M1;
p=H[sol1];
while(p!=NULL)
{
if(p->nod1==sol1&&p->nod2==sol2)
{
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+M2-string[i-m-1]+string[i])%M2;
p=H[sol1];
while(p!=NULL)
{
if(p->nod1==sol1&&p->nod2==sol2)
{
nr++;
break;
}
p=p->link;
}
}
printf("%d\n",nr);
return 0;
}