Pagini recente » Cod sursa (job #2814540) | Cod sursa (job #3130464) | camelia_01 | Cod sursa (job #2092152) | Cod sursa (job #98543)
Cod sursa(job #98543)
#include <cstdio>
#include <cstring>
const int maxn = 10000002;
const int maxl = 30;
const int maxc = 50001;
const int maxp = 666013;
FILE *in = fopen("abc2.in","r"), *out = fopen("abc2.out","w");
char a[maxn];
int p[maxn];
int n, m;
char c[maxl];
int h[maxp];
int pow(int a, int b)
{
int s = 1;
for ( int i = 1; i <= b; ++i )
s *= a;
return s;
}
int getnr()
{
int r = 0;
int k = n - 1;
for ( int i = 0; i < n; ++i )
r = (r + (c[i]-'a')*pow(3,k--)) % maxp;
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--)) % maxp;
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;
}
//int getpref()
//{
// p[1] = 0;
//
// int k = 0;
// int i;
// for ( i = 2; c[i]; ++i )
// {
// while ( k > 0 && c[k+1] != c[i] )
// k = p[k];
//
// if ( c[k+1] == c[i] )
// ++k;
//
// p[i] = k;
// }
//
// n = i-1;
//}
//
//char viz[maxn];
//int main()
//{
// fscanf(in, "%s", a+1);
//
// int cnt = 0;
// while ( fscanf(in, "%s", c+1) == 1 )
// {
// int q = 0;
// getpref();
//
// for ( int i = 1; a[i]; ++i )
// {
// while ( q > 0 && c[q+1] != a[i] )
// q = p[q];
// if ( c[q+1] == a[i] )
// ++q;
//
// if ( q == n && !viz[i-n+1] )
// ++cnt, viz[i-n+1] = 1;
// }
// }
//
// fprintf(out, "%d\n", cnt);
//
// return 0;
//}