Pagini recente » Cod sursa (job #737964) | Cod sursa (job #836499) | Cod sursa (job #1562489) | Cod sursa (job #722972) | Cod sursa (job #2700532)
#include <fstream>
#include <cstring>
#include <cmath>
using namespace std;
const int N = 1e7;
const int LMAX = 20;
const int MOD = 90907;
char s[N + 1], cuv[LMAX + 1];
int lst[MOD], urm[N + 1], val[N + 1], nr = 0, ls, lcuv;
bool exista(unsigned x) {
int c = x % MOD, p = lst[c];
while (p && val[p]!= x)
p = urm[p];
return p;
}
void adauga(unsigned x) {
if (exista(x))
return;
int c = x % MOD;
val[++nr] = x;
urm[nr] = lst[c];
lst[c] = nr;
}
unsigned hash_cuv() {
unsigned h = 0;
for (int i = 0; i < lcuv; ++i)
h = h * 3 + (cuv[i] - 'a');
return h;
}
int main() {
ifstream in("abc2.in");
ofstream out("abc2.out");
in >> s >> cuv;
ls = strlen(s), lcuv = strlen(cuv);
if (ls < lcuv) {
out << '0';
in.close();
out.close();
return 0;
}
unsigned h;
do {
h = hash_cuv();
adauga(h);
} while (in >> cuv);
int rez = 0;
h = 0;
for (int i = 0; i < lcuv; ++i)
h = h * 3 + (s[i] - 'a');
if (exista(h))
++rez;
unsigned p3 = pow(3, lcuv - 1);
for (int i = lcuv; i < ls; ++i) {
h %= p3;
h = h * 3 + (s[i] - 'a');
if (exista(h))
++rez;
}
out << rez;
in.close();
out.close();
return 0;
}