Pagini recente » Cod sursa (job #1063194) | Cod sursa (job #1091859) | Cod sursa (job #2146452) | Cod sursa (job #2246094) | Cod sursa (job #167904)
Cod sursa(job #167904)
#include <cstdio>
#include <cstring>
const int maxn = 10000002;
const int maxl = 30;
const int maxc = 50001;
const int hmod = 666013;
FILE *in = fopen("abc2.in","r"), *out = fopen("abc2.out","w");
char a[maxn];
int n, m;
char c[maxl];
int h[hmod];
int pow(int x, int y)
{
if ( y == 0 )
return 1;
if ( y == 1 )
return x % hmod;
long long t = pow(x, y >> 1);
if ( (y & 1) )
return (long long)(((long long)(t * t) % hmod) * x) % hmod;
return (long long)(t * t) % hmod;
}
int getnr()
{
int r = 0;
int k = n - 1;
for ( int i = 0; i < n; ++i )
r = (r + (c[i]-'a')*pow(3,k--)) % hmod;
return r;
}
int check(int x, int y)
{
int r = 0;
int k = n - 1;
for ( int i = x; i < y; ++i )
r = (r + (a[i]-'a')*pow(3,k--)) % hmod;
return r;
}
int cnt;
int main()
{
fscanf(in, "%s", a);
m = strlen(a);
fscanf(in, "%s", c);
n = strlen(c);
++h[ getnr() ];
// printf("%d\n", getnr());
while ( fscanf(in, "%s", c) == 1 )
++h[ getnr() ];//, printf("%d\n", getnr());;
//printf("\n\n");
for ( int i = 0; i < m; ++i )
{
int k = i + n;
if ( k > m )
break;
//printf("%d\n", check(i, k));
if ( h[ check(i, k) ] )
++cnt;
}
fprintf(out, "%d\n", cnt);
return 0;
}