Cod sursa(job #177393)
#include<cstdio>
#include<cstring>
const int hash1=1009;
const int hash2=1013;
const int hash3=11003;
int a[hash1][hash2][10],l,x,y,z,nr,n,c1,c2,c3,i;
char s[10000000],s2[21];
inline bool seek()
{
for(int j=1;j<=a[x][y][0];j++)
if(a[x][y][j]==z) return 1;
return 0;
}
int main()
{
freopen("abc2.in","r",stdin);
freopen("abc2.out","w",stdout);
gets(s);
gets(s2);
l=strlen(s2);
goto calc;
while(!feof(stdin))
{
gets(s2);
calc:
x=y=z=0;
for(i=0;i<l;i++)
{
x*=3;y*=3;z*=3;
x+=s2[i]-'a';
y+=s2[i]-'a';
z+=s2[i]-'a';
while(x>=hash1) x-=hash1;
while(y>=hash2) y-=hash2;
while(z>=hash3) z-=hash3;
}
if(!seek()) a[x][y][++a[x][y][0]]=z;
}
n=strlen(s);
x=y=z=0;c1=c2=c3=1;
for(i=0;i<l;i++)
{
s[i]-='a';
if(i<l-1)
{
c1*=3;
c2*=3;
c3*=3;
while(c1>=hash1) c1-=hash1;
while(c2>=hash2) c2-=hash2;
while(c3>=hash3) c3-=hash3;
}
x*=3;y*=3;z*=3;
x+=s[i];
y+=s[i];
z+=s[i];
while(x>=hash1) x-=hash1;
while(y>=hash2) y-=hash2;
while(z>=hash3) z-=hash3;
}
if(seek()) nr++;
for(;i<n;i++)
{
s[i]-='a';
x-=c1*s[i-l];
y-=c2*s[i-l];
z-=c3*s[i-l];
while(x<0) x+=hash1;
while(y<0) x+=hash2;
while(z<0) x+=hash3;
x*=3;y*=3;z*=3;
x+=s[i];y+=s[i];z+=s[i];
while(x>=hash1) x-=hash1;
while(y>=hash2) y-=hash2;
while(z>=hash3) z-=hash3;
if(seek())nr++;
}
printf("%d\n",nr);
fclose(stdout);
return 0;
}