Cod sursa(job #2700532)

Utilizator iancupoppPopp Iancu Alexandru iancupopp Data 27 ianuarie 2021 22:31:44
Problema Abc2 Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.36 kb
#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;
}