Pagini recente » Cod sursa (job #599499) | Cod sursa (job #2918592) | Cod sursa (job #648035) | Cod sursa (job #1486096) | Cod sursa (job #497393)
Cod sursa(job #497393)
#include <stdio.h>
#include <string.h>
int n,m,nr,sol,pow,i,M,solx;
struct hash
{
int nod,nodx;
hash *link;
}*H[100000];
char str[10000005],s[22];
inline void add(int x,int xx)
{
hash *p;
p=new hash;
p->nod=x;
p->nodx=xx;
p->link=H[x%M];
H[x%M]=p;
}
inline int src(int x,int xx)
{
hash *p;
p=H[x%M];
while(p!=NULL)
{
if(p->nod==x&&p->nodx==xx) return 1;
p=p->link;
}
return 0;
}
int main()
{
freopen("abc2.in","r",stdin);
freopen("abc2.out","w",stdout);
fgets(str,10000005,stdin);
M=39967;
n=strlen(str)-1;
if(str[n]=='\n') n--;
fgets(s,22,stdin);
m=strlen(s)-1;
if(s[m]=='\n') m--;
sol=0;
solx=0;
for(i=0;i<=m;i++)
{
sol=((sol*3)%M+s[i])%M;
solx=0;
}
if(src(sol,solx)==0) add(sol,solx);
while(!feof(stdin))
{
fgets(s,25,stdin);
if(!feof(stdin))
{
sol=0;
solx=0;
for(i=0;i<=m;i++)
{
sol=((sol*3)%M+s[i])%M;
solx=0;
}
if(src(sol,solx)==0) add(sol,solx);
}
}
sol=0;
solx=0;
pow=1;
nr=0;
for(i=1;i<=m;i++)
pow=(pow*3)%M;
for(i=0;i<=m;i++)
{
sol=((sol*3)%M+str[i])%M;
solx=0;
}
if(src(sol,solx)) nr++;
for(i=m+1;i<=n;i++)
{
sol=((sol+M-(pow*str[i-m-1])%M)*3+str[i])%M;
solx=0;
if(src(sol,solx)) nr++;
}
printf("%d\n",nr);
return 0;
}