Pagini recente » Cod sursa (job #3031015) | Cod sursa (job #3003842) | Cod sursa (job #3173860) | Cod sursa (job #451466) | Cod sursa (job #498351)
Cod sursa(job #498351)
#include <stdio.h>
#include <string.h>
unsigned int m,n,i,pos,sol,pow,nr,M,pw;
char string[10000010],s[25];
struct hash
{
unsigned int nod;
hash *link;
}*H[700000];
inline void add(unsigned int pos,unsigned int sol)
{
hash *p;
p=new hash;
p->nod=sol;
p->link=H[pos];
H[pos]=p;
}
inline int find(unsigned int pos,unsigned int sol)
{
hash *p;
p=H[pos];
while(p!=NULL)
{
if(p->nod==sol) return 1;
p=p->link;
}
return 0;
}
int main()
{
freopen("abc2.in","r",stdin);
freopen("abc2.out","w",stdout);
fgets(string,10000010,stdin);
n=strlen(string)-2;
M=666013;
fgets(s,25,stdin);
m=strlen(s)-2;
pos=0;
sol=0;
for(i=0;i<=m;i++)
{
pos*=3;
sol*=3;
pos+=s[i]-'a';
sol+=s[i]-'a';
pos%=M;
}
add(pos,sol);
while(!feof(stdin))
{
fgets(s,25,stdin);
pos=0;
sol=0;
for(i=0;i<=m;i++)
{
pos*=3;
sol*=3;
pos+=s[i]-'a';
sol+=s[i]-'a';
pos%=M;
}
add(pos,sol);
}
pos=0;
sol=0;
for(i=0;i<=m;i++)
{
pos*=3;
sol*=3;
pos+=string[i]-'a';
sol+=string[i]-'a';
pos%=M;
}
add(pos,sol);
pow=1;
pw=1;
for(i=1;i<=m;i++)
{
pow*=3;
pow%=M;
pw*=3;
}
nr=0;
if(find(pos,sol)) nr++;
for(i=m+1;i<=n;i++)
{
pos+=M;
pos-=pow*(string[i-m-1]-'a');
pos*=3;
pos+=string[i]-'a';
pos%=M;
sol-=pw*(string[i-m-1]-'a');
sol*=3;
sol+=string[i]-'a';
if(find(pos,sol)) nr++;
}
printf("%d\n",nr);
return 0;
}