Pagini recente » Cod sursa (job #2190931) | Cod sursa (job #1784) | Autentificare | Cod sursa (job #901540) | Cod sursa (job #170242)
Cod sursa(job #170242)
#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 )
s = (unsigned int)s + p[i]*(c[j][i] - 'a');
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;
}
if ( h[st] == what )
return 1;
return 0;
}
int cnt;
int main()
{
read();
getnr();
++j;
while ( fgets(c[j], 100, in) )
getnr(), ++j;
--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;
int ph = p[0];
for ( int i = m; i < n; ++i )
{
s = (unsigned int)s - (ph * (a[i-m] - 'a'));
s = (unsigned int)s * base;
s = (unsigned int)s + (a[i] - 'a');
if ( search(s) )
++cnt;
}
fprintf(out, "%d\n", cnt);
return 0;
}