Cod sursa(job #2700505)

Utilizator iancupoppPopp Iancu Alexandru iancupopp Data 27 ianuarie 2021 21:45:25
Problema Abc2 Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.71 kb
#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;
}