Pagini recente » Cod sursa (job #2197906) | Cod sursa (job #1990750) | Cod sursa (job #2595279) | Cod sursa (job #1851046) | Cod sursa (job #108099)
Cod sursa(job #108099)
#include <cstdio>
#include <algorithm>
using namespace std;
const int Lmax = 10000005;
const int Dmax = 32;
const int Wmax = 50005;
char s[Lmax];
char word[Dmax];
int N, M;
int Nr_cuv;
unsigned int v[Wmax];
int stp;
int search(unsigned int cuv) {
int step = stp, p = 1;
for (; step; step >>= 1)
if (p+step <= Nr_cuv && v[p+step] <= cuv) p += step;
return v[p] == cuv;
}
int main() {
freopen("abc2.in", "r", stdin);
freopen("abc2.out", "w", stdout);
fgets(s, Lmax, stdin);
N = strlen(s)-1;
while (fgets(word, Dmax, stdin)) {
M = strlen(word)-1;
unsigned int code = 0;
for (int i = 0; i < M; ++i)
code = code*3 + word[i]-'a';
v[++Nr_cuv] = code;
}
sort(v+1, v+Nr_cuv+1);
stp = 1;
while (2*stp < Nr_cuv) stp <<= 1;
unsigned int code = 0;
unsigned int pow = 1;
for (int i = 1; i < M; ++i)
pow *= 3;
int ret = 0;
for (int i = 0; i < M; ++i)
code = code*3 + s[i]-'a';
ret += search(code);
for (int i = M; i < N; ++i) {
code -= pow * (s[i-M]-'a');
code = code*3 + s[i]-'a';
ret += search(code);
}
printf("%d\n", ret);
}