Pagini recente » Istoria paginii runda/oji2005_clasa_a_9_a/clasament | Cod sursa (job #587345) | Cod sursa (job #373225) | Cod sursa (job #1265981) | Cod sursa (job #170232)
Cod sursa(job #170232)
#include <cstdio>
#include <algorithm>
const int maxn = 10000002;
const int maxc = 50001;
const int maxl = 21;
const int base = 3;
FILE *in = fopen("abc2.in","r"), *out = fopen("abc2.out","w");
int n, m;
char a[maxn];
char c[maxc][maxl];
unsigned int h[maxc]; // h[i] = cuvantul i in baza base
int j = 1;
int p[maxl];
int pow(int a, int b)
{
int s = 1;
for ( int i = 1; i <= b; ++i )
s = s * a;
return s;
}
void read()
{
fgets(a, sizeof(a), in);
n = strlen(a) - 1;
fgets(c[1], 100, in);
m = strlen(c[1]) - 1;
for ( int i = 0; i < m; ++i )
p[i] = pow(base, m - i - 1);
}
void getnr()
{
unsigned int s = 0;
for ( int i = 0; i < m; ++i )
{
c[j][i] = c[j][i] - 'a';
s = s + p[i]*c[j][i];
}
h[j] = s;
}
int search(unsigned int what)
{
int st = 1;
int m = 0;
int dr = j;
while ( st < dr )
{
m = (st + dr) >> 1;
if ( h[m] == what )
return 1;
else if ( h[m] > what )
dr = m;
else
st = m + 1;
}
return 0;
}
int cnt;
int main()
{
read();
getnr();
++j;
while ( fgets(c[j], 100, in) )
getnr(), ++j;
std::sort(h + 1, h + j + 1);
unsigned int s = 0;
for ( int i = 0; i < m; ++i )
s = s + p[i]*(a[i] - 'a');
if ( search(s) )
++cnt;
for ( int i = m; i < n; ++i )
{
s = s - (p[0] * (a[i-m] - 'a'));
s *= base;
s = s + (a[i] - 'a');
if ( search(s) )
++cnt;
}
fprintf(out, "%d\n", cnt);
return 0;
}