Cod sursa(job #2700456)

Utilizator iancupoppPopp Iancu Alexandru iancupopp Data 27 ianuarie 2021 18:45:01
Problema Abc2 Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.72 kb
#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, long long 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, long long 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, long long 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);
    long long hash = 0;
    for (int i = 0; i < lencuv; ++i)
        hash = hash * 3 + (s[i] - 'a');
    adauga(0, hash);
    long long 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);
    }
    long long rez = 0;
    while (in >> cuv) {
        hash = calcHash(cuv, lencuv);
        rez += aparitii(cuv, hash);
    }
    out << rez;

    in.close();
    out.close();
    return 0;
}