Cod sursa(job #2300814)

Utilizator BlackLordFMI Alex Oprea BlackLord Data 12 decembrie 2018 08:43:35
Problema Abc2 Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.41 kb
#include <fstream>
#include <cstring>
#include <vector>

using namespace std;

ifstream fin ("abc2.in");
ofstream fout ("abc2.out");

const int mod = 10041, N = 10001010, M = 30;

unsigned int n, len_cuv, len_text, x, i, cnt, nr, pow;
char text[N], cuv[M];

vector<unsigned int> L[mod + 10];

void hashing() {
    x = 0;
    for (i = 0 ; i < len_cuv; ++i) {
        x = x * 3 + (cuv[i] - 'a');
    }
    if (x == 0) {
        nr = 0;
    } else {
        nr = x % mod;
    }
    for (auto it:L[nr]) {
        if (it == x){
            return;
        }
    }
    L[nr].push_back(x);
}

void verifica(unsigned int x) {
    if (x == 0) {
        nr = 0;
    } else {
        nr = x % mod;
    }
    if (nr < 0) {
        exit(0);
    }
    for (auto it:L[nr]) {
        if (it == x){
            cnt++;
            return;
        }
    }
}
int main() {
    fin >> text;
    len_text = strlen(text);
    fin >> cuv;
    len_cuv = strlen(cuv);
    hashing();
    while(fin >> cuv) {
        hashing();
    }
    x = 0;
    pow = 1;
    for(i = 1; i < len_cuv; ++i) {
        pow = pow * 3;
    }
    for(i = 0; i < len_cuv - 1; ++i) {
        x = x * 3 + (text[i] - 'a');
    }
    for(i = len_cuv - 1; i < len_text; ++i) {
        x = x * 3 + (text[i] - 'a');
        verifica(x);
        x = x - pow * (text[i - len_cuv + 1] - 'a');
    }
    fout << cnt;
    return 0;
}