Pagini recente » Cod sursa (job #2765506) | Cod sursa (job #2365261) | Cod sursa (job #1821693) | Cod sursa (job #2323717) | Cod sursa (job #240951)
Cod sursa(job #240951)
#include <stdio.h>
#include <math.h>
#include <algorithm>
#define LMAX 10000010
#define DMAX 64
#define MAXN 50010
using namespace std;
long i, n, m, cuv, stp, num, p, sol;
char s[LMAX], word[DMAX];
long v[MAXN];
long search(long cuv);
void read_data();
int main() {
freopen("abc2.in", "r", stdin);
freopen("abc2.out", "w", stdout);
read_data();
sort(v + 1, v + cuv + 1);
stp = 1;
while (2 * stp < cuv) {
stp <<= 1;
}
num = 0;
p = 1;
for (i = 1; i < m; ++i) {
p *= 3;
}
for (i = 0; i < m; ++i) {
num = num * 3 + s[i] - 'a';
}
sol += search(num);
for (i = m; i < n; ++i) {
num -= p * (s[i - m] - 'a');
num = num * 3 + s[i] - 'a';
sol += search(num);
}
printf("%ld\n", sol);
return 0;
}
long search(long cuv) {
long step = stp, p = 1;
for (; step; step >>= 1) {
if (p + step <= cuv && v[p + step] <= cuv) {
p += step;
}
}
if (v[p] == cuv) {
return 1;
} else {
return 0;
}
}
void read_data() {
fgets(s, LMAX, stdin);
n = strlen(s) - 1;
while (fgets(word, DMAX, stdin)) {
m = strlen(word) - 1;
long num = 0;
for (i = 0; i < m; ++i) {
num = num * 3 + word[i] - 'a';
}
v[++cuv] = num;
}
}