Pagini recente » Cod sursa (job #1753597) | Cod sursa (job #2930082) | Cod sursa (job #445654) | Cod sursa (job #2310594) | Cod sursa (job #2700505)
#include <fstream>
#include <cstring>
#include <cmath>
using namespace std;
const int N = 1e7;
const int LMAX = 20;
const int MOD = 3145739;
char s[N + 1], cuv[LMAX + 1];
int lst[MOD], urm[N + 1], nr = 0, ls, lcuv;
pair<unsigned, int> val[N + 1];
int cauta(unsigned x) {
int c = x % MOD, p = lst[c];
while (p && val[p].first != x)
p = urm[p];
if (p)
return p;
return -1;
}
void adauga(unsigned x) {
int p = cauta(x), c = x % MOD;
if (p == -1) {
val[++nr] = { x, 1 };
urm[nr] = lst[c];
lst[c] = nr;
}
else
++val[p].second;
}
void init_hash() {
unsigned h = 0;
for (int i = 0; i < lcuv; ++i)
h = h * 3 + (s[i] - 'a');
adauga(h);
unsigned p3 = pow(3, lcuv - 1);
for (int i = lcuv; i < ls; ++i) {
h %= p3;
h = h * 3 + (s[i] - 'a');
adauga(h);
}
}
unsigned hash_cuv() {
unsigned h = 0;
for (int i = 0; i < lcuv; ++i)
h = h * 3 + (cuv[i] - 'a');
return h;
}
int count(unsigned x) {
int p = cauta(x);
if (p != -1) {
int ret = val[p].second, c = x % MOD;
swap(val[p], val[lst[c]]);
lst[c] = urm[lst[c]];
return ret;
}
return 0;
}
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;
}
init_hash();
unsigned h, rez = 0;
do {
h = hash_cuv();
rez += count(h);
} while (in >> cuv);
out << rez;
in.close();
out.close();
return 0;
}