Pagini recente » Cod sursa (job #1939194) | Borderou de evaluare (job #105061) | Cod sursa (job #1591800) | Cod sursa (job #413160) | Cod sursa (job #102423)
Cod sursa(job #102423)
#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 search(int st, int dr, unsigned int cuv) {
int m;
while (st != dr) {
m = (st+dr+1)/2;
if (v[m] <= cuv) st = m;
else dr = m-1;
}
return v[st] == 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);
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(1, Nr_cuv, code);
for (int i = M; i < N; ++i) {
code -= pow * (s[i-M]-'a');
code = code*3 + s[i]-'a';
ret += search(1, Nr_cuv, code);
}
printf("%d\n", ret);
}