Pagini recente » Cod sursa (job #2560490) | Cod sursa (job #393547) | Cod sursa (job #1475611) | Cod sursa (job #1579365) | Cod sursa (job #497205)
Cod sursa(job #497205)
#include <stdio.h>
#include <string.h>
long n,m,nr,sol1,pow1,i,M1,M2,sol2,pow2;
struct hash
{
long nod;
hash *link;
}*H1[45000],*H2[45000];
char str[10000005],s[25];
void add1(long x)
{
hash *p;
p=new hash;
p->nod=x;
p->link=H1[x%M1];
H1[x%M1]=p;
}
long src1(long x)
{
hash *p;
p=H1[x%M1];
while(p!=NULL)
{
if(p->nod==x) return 1;
p=p->link;
}
return 0;
}
void add2(long x)
{
hash *p;
p=new hash;
p->nod=x;
p->link=H2[x%M2];
H2[x%M2]=p;
}
long src2(long x)
{
hash *p;
p=H2[x%M2];
while(p!=NULL)
{
if(p->nod==x) return 1;
p=p->link;
}
return 0;
}
int main()
{
freopen("abc2.in","r",stdin);
freopen("abc2.out","w",stdout);
fgets(str,10000005,stdin);
M1=44027;
M2=44017;
n=strlen(str)-1;
if(str[n]=='\n') n--;
fgets(s,25,stdin);
m=strlen(s)-1;
if(s[m]=='\n') m--;
sol1=0;
sol2=0;
for(i=0;i<=m;i++)
{
sol1=((sol1*4)%M1+s[i]-'a')%M1;
sol2=((sol2*4)%M2+s[i]-'a')%M2;
}
if(src1(sol1)==0) add1(sol1);
if(src2(sol2)==0) add2(sol2);
while(!feof(stdin))
{
fgets(s,25,stdin);
if(!feof(stdin))
{
sol1=0;
sol2=0;
for(i=0;i<=m;i++)
{
sol1=((sol1*4)%M1+s[i]-'a')%M1;
sol2=((sol2*4)%M2+s[i]-'a')%M2;
}
if(src1(sol1)==0) add1(sol1);
if(src2(sol2)==0) add2(sol2);
}
}
sol1=0;
sol2=0;
pow1=1;
pow2=1;
nr=0;
for(i=1;i<=m;i++)
{
pow1=(pow1*4)%M1;
pow2=(pow2*4)%M2;
}
for(i=0;i<=m;i++)
{
sol1=((sol1*4)%M1+str[i]-'a')%M1;
sol2=((sol2*4)%M2+str[i]-'a')%M2;
}
if(src1(sol1)&&src2(sol2)) nr++;
for(i=m+1;i<=n;i++)
{
sol1=(((sol1+M1-(pow1*(str[i-m-1]-'a'))%M1)%M1)*4+(str[i]-'a'))%M1;
sol2=(((sol2+M2-(pow2*(str[i-m-1]-'a'))%M2)%M2)*4+(str[i]-'a'))%M2;
if(src1(sol1)&&src2(sol2)) nr++;
}
printf("%ld\n",nr);
return 0;
}