Pagini recente » Cod sursa (job #2499708) | Cod sursa (job #470732) | Cod sursa (job #844066) | Cod sursa (job #680091) | Cod sursa (job #2295966)
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <iostream>
using namespace std;
const int maxn = 10000002;
const int maxc = 50001;
const int maxl = 21;
const int base = 3;
int n, m, cnt, j = 1, p[maxl];
char a[maxn],c[maxl];
int h[maxc]; // h[i] = cuvantul i in baza base
int pow(int a, int b)
{
int s = 1, i;
for (i = 1; i <= b; ++i )
s = s * a;
return s;
}
void getnr()
{
int s = 0, i;
for (i = 0; i < m; ++i )
s = s + p[i]*(c[i] - 'a');
h[j] = s;
}
int caut(int x)
{
int st = 1, m = 0, dr = j;
while ( st < dr )
{
m = (st + dr) >> 1;
if ( h[m] == x )
return 1;
else if ( h[m] > x )
dr = m;
else
st = m + 1;
}
if ( h[st] == x )
return 1;
return 0;
}
int main()
{
FILE *in = fopen("abc2.in","r");
FILE *out = fopen("abc2.out","w");
int ph, s = 0 ,i;
fgets(a, maxn, in);
n = strlen(a) - 1;
fgets(c, 100, in);
m = strlen(c) - 1;
for (i = 0; i < m; ++i )
p[i] = pow(base, m - i - 1);
getnr();
++j;
while ( fgets(c, 100, in) ){
getnr();
++j;
}
--j;
sort(h + 1, h + j + 1);
for (i = 0; i < m; ++i )
s = s + p[i]*(a[i] - 'a');
if ( caut(s) )
++cnt;
ph = p[0];
for (i = m; i < n; ++i )
{
s = s - (ph * (a[i-m] - 'a'));
s = s * base;
s = s + (a[i] - 'a');
if ( caut(s) )
++cnt;
}
fprintf(out, "%d\n", cnt);
fclose(in);
fclose(out);
return 0;
}