Pagini recente » Istoria paginii runda/oji-10-2/clasament | Cod sursa (job #3031619) | Cod sursa (job #1145534) | Cod sursa (job #637094) | Cod sursa (job #167916)
Cod sursa(job #167916)
#include <cstdio>
#include <cstring>
const int maxn = 10000002;
const int maxl = 30;
const int maxc = 50001;
const int hmod = 666013;
const int base = 3;
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 a, int b)
{
int s = 1;
for ( int i = 1; i <= b; ++i )
s *= a,
s %= hmod;
return s;
}
int getnr()
{
unsigned int r = 0;
int k = n - 1;
for ( int i = 0; i < n; ++i )
{
//r = (r + (c[i] - 'a')*pow(base, k--)) % hmod;
r += c[i];
r += ( r << 10 );
r ^= ( r >> 6 );
}
r += ( r << 3 );
r ^= ( r >> 11 );
r += ( r << 15 );
return r % hmod;
}
int check(int x, int y)
{
unsigned int r = 0;
int k = n - 1;
for ( int i = x; i < y; ++i )
{
//r = (r + (a[i] - 'a')*pow(base, k--)) % hmod;
r += a[i];
r += ( r << 10 );
r ^= ( r >> 6 );
}
r += ( r << 3 );
r ^= ( r >> 11 );
r += ( r << 15 );
return r % hmod;
}
int cnt;
int main()
{
fscanf(in, "%s", a);
m = strlen(a);
fscanf(in, "%s", c);
n = strlen(c);
++h[ getnr() ];
while ( fscanf(in, "%s", c) == 1 )
++h[ getnr() ];
for ( int i = 0; i < m; ++i )
{
int k = i + n;
if ( k > m )
break;
if ( h[ check(i, k) ] )
++cnt;
}
fprintf(out, "%d\n", cnt);
return 0;
}