Pagini recente » Cod sursa (job #2088695) | Cod sursa (job #1196923) | Cod sursa (job #1398018) | Cod sursa (job #1148689) | Cod sursa (job #497562)
Cod sursa(job #497562)
#include <stdio.h>
#include <string.h>
struct hash
{
int nod1,nod2;
hash *link;
}*H[100100];
int nr,n,m,i,sol1,sol2,M1,M2,pow1,pow2;
hash *p;
char string[1000010],s[25];
int main()
{
freopen("abc2.in","r",stdin);
freopen("abc2.out","w",stdout);
fgets(string,1000010,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=100007;
for(i=0;i<=m;i++)
{
sol1=((sol1*M1)%M1+s[i]-'a')%M1;
sol2=((sol2*M2)%M2+s[i]-'a')%M2;
}
nr=0;
p=H[sol1%M1];
while(p!=NULL)
{
if(p->nod1==sol1&&p->nod2==sol2)
{
nr=1;
break;
}
p=p->link;
}
if(nr==0)
{
p=new hash;
p->nod1=sol1;
p->nod2=sol2;
p->link=H[sol1%M1];
H[sol1%M1]=p;
}
while(!feof(stdin))
{
fgets(s,25,stdin);
sol1=0;
sol2=0;
for(i=0;i<=m;i++)
{
sol1=((sol1*M1)%M1+s[i]-'a')%M1;
sol2=((sol2*M2)%M2+s[i]-'a')%M2;
}
nr=0;
p=H[sol1%M1];
while(p!=NULL)
{
if(p->nod1==sol1&&p->nod2==sol2)
{
nr=1;
break;
}
p=p->link;
}
if(nr==0)
{
p=new hash;
p->nod1=sol1;
p->nod2=sol2;
p->link=H[sol1%M1];
H[sol1%M1]=p;
}
}
nr=0;
sol1=0;
sol2=0;
for(i=0;i<=m;i++)
{
sol1=((sol1*M1)%M1+string[i]-'a')%M1;
sol2=((sol2*M2)%M2+string[i]-'a')%M2;
}
pow1=1;
pow2=1;
for(i=1;i<=m;i++)
{
pow1=(pow1*M1)%M1;
pow2=(pow2*M2)%M2;
}
for(i=m+1;i<=n;i++)
{
sol1=(((sol1+M1-(pow1*(string[i-m-1]-'a'))%M1)*M1)%M1+string[i]-'a')%M1;
sol2=(((sol2+M2-(pow1*(string[i-m-1]-'a'))%M2)*M2)%M2+string[i]-'a')%M2;
p=H[sol1%M1];
while(p!=NULL)
{
if(p->nod1==sol1&&p->nod2==sol2)
{
nr++;
break;
}
p=p->link;
}
}
printf("%d\n",nr);
return 0;
}