Cod sursa(job #3318143)

Utilizator TimofeiFilipTimofei Filip Emanuel TimofeiFilip Data 27 octombrie 2025 12:26:24
Problema Abc2 Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.23 kb
#include <bits/stdc++.h>
using namespace std;

const int NMAX = 10000005;
const long long BASE1 = 131;
const long long MOD1 = 1000000007;
const long long BASE2 = 137;
const long long MOD2 = 1000000009;
const char HASHER = 'a' - 1;

char A[NMAX], B[25];
long long powers1[25], powers2[25];

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

void PrecomputePowers(int n) {
    powers1[0] = powers2[0] = 1;
    for (int i = 1; i <= n; i++) {
        powers1[i] = (powers1[i - 1] * BASE1) % MOD1;
        powers2[i] = (powers2[i - 1] * BASE2) % MOD2;
    }
}

pair<long long, long long> HashEntireString(const char s[], int n) {
    long long h1 = 0, h2 = 0;
    for (int i = 0; i < n; i++) {
        h1 = (h1 * BASE1 + (s[i] - HASHER)) % MOD1;
        h2 = (h2 * BASE2 + (s[i] - HASHER)) % MOD2;
    }
    return {h1, h2};
}

int main() {
    ios_base::sync_with_stdio(false);
    fin.tie(nullptr);
    fout.tie(nullptr);

    fin >> A;
    int n = strlen(A);

    vector<string> cuvinte;
    while (fin >> B) cuvinte.push_back(string(B));

    if (cuvinte.empty()) {
        fout << 0 << "\n";
        return 0;
    }

    int L = cuvinte[0].size();
    if (n < L) {
        fout << 0 << "\n";
        return 0;
    }

    PrecomputePowers(L);

    unordered_set<long long> dict;
    dict.reserve(cuvinte.size() * 2);
    for (auto &w : cuvinte)
        if ((int)w.size() == L) {
            auto h = HashEntireString(w.c_str(), L);
            long long combined = h.first * MOD2 + h.second;
            dict.insert(combined);
        }

    auto h_window = HashEntireString(A, L);
    long long current = h_window.first * MOD2 + h_window.second;
    long long count = 0;
    if (dict.find(current) != dict.end()) count++;

    for (int i = L; i < n; i++) {
        h_window.first = (h_window.first - (A[i - L] - HASHER) * powers1[L - 1] % MOD1 + MOD1) % MOD1;
        h_window.first = (h_window.first * BASE1 + (A[i] - HASHER)) % MOD1;

        h_window.second = (h_window.second - (A[i - L] - HASHER) * powers2[L - 1] % MOD2 + MOD2) % MOD2;
        h_window.second = (h_window.second * BASE2 + (A[i] - HASHER)) % MOD2;

        current = h_window.first * MOD2 + h_window.second;
        if (dict.find(current) != dict.end()) count++;
    }

    fout << count << "\n";
    return 0;
}