Pagini recente » Cod sursa (job #2923182) | Cod sursa (job #1704389) | Cod sursa (job #1833720) | Cod sursa (job #64665) | Cod sursa (job #2700450)
#include <fstream>
#include <cstring>
#include <cmath>
using namespace std;
const int N = 1e7;
const int LMAX = 20;
const int MOD = 666019;
pair<int, int> val[N + 1];
int lst[MOD], urm[N + 1], nr = 0, len, lencuv;
char s[N], cuv[LMAX + 1];
int cauta(int x, unsigned hash) {
int cod = hash % MOD;
int p = lst[cod];
while (p && val[p].first != x)
p = urm[p];
if (p)
return p;
return -1;
}
int aparitii(char* str, unsigned hash) {
int cod = hash % MOD;
int p = lst[cod];
while (p && strncmp(str, s + val[p].first, lencuv))
p = urm[p];
if (p)
return val[p].second;
return 0;
}
void adauga(int x, unsigned hash) {
int cod = hash % MOD;
int p = cauta(x, cod);
if (p == -1) {
val[++nr] = { x, 1 };
urm[nr] = lst[cod];
lst[cod] = nr;
}
else
++val[p].second;
}
int calcHash(char* str, int len) {
int hash = 0;
for (int i = 0; i < len; ++i)
hash = hash * 3 + (str[i] - 'a');
return hash;
}
int main() {
ifstream in("abc2.in");
ofstream out("abc2.out");
in >> s >> cuv;
len = strlen(s), lencuv = strlen(cuv);
unsigned hash = 0;
for (int i = 0; i < lencuv; ++i)
hash = hash * 3 + (s[i] - 'a');
adauga(0, hash);
int p3 = pow(3, lencuv - 1);
for (int i = lencuv; i < len; ++i) {
hash = hash % p3;
hash = hash * 3 + (s[i] - 'a');
adauga(i - lencuv + 1, hash);
}
int rez = 0;
while (in >> cuv) {
hash = calcHash(cuv, lencuv);
rez += aparitii(cuv, hash);
}
out << rez;
in.close();
out.close();
return 0;
}