Cod sursa(job #3266654)

Utilizator Barbu_MateiBarbu Matei Barbu_Matei Data 9 ianuarie 2025 18:51:08
Problema Abc2 Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.34 kb
#include <bits/stdc++.h>
using namespace std;

const int p = 3, MOD = 66013;
string text, word;
vector<unsigned int> m[MOD];

bool searchHash(unsigned int k) {
    int r = k % MOD;
    for (int i = 0; i < m[r].size(); ++i) {
        if (m[r][i] == k) {
            return 1;
        }
    }
    return 0;
}

void insertHash(unsigned int k) {
    int r = k % MOD;
    if (!searchHash(k)) {
         m[r].push_back(k);
    }
}

unsigned int hashF(string word) {
    unsigned int res = 0;
    for (int i = 0; i < word.size(); ++i) {
        res = res * p + (word[i] - 'a');
    }
    return res;
}

unsigned int calcPow(int base, int power) {
    unsigned int res = 1;
    for (int i = 1; i <= power; ++i) {
        res *= base;
    }
    return res;
}

int main() {
    ifstream cin("abc2.in");
    ofstream cout("abc2.out");
    cin >> text;
    while (cin >> word) {
        insertHash(hashF(word));
    }
    int wSize = word.size();
    unsigned int res = 0, pos = 0, ans = 0;
    unsigned int last = calcPow(3, wSize - 1);
    for (int i = 0; i < text.size(); ++i) {
        res = res * p + (text[i] - 'a');
        if (i >= wSize - 1) {
            if (searchHash(res)) {
                ++ans;
            }
            res = res - last * (text[i - (wSize - 1)] - 'a');
        }
    }
    cout << ans;
}