Cod sursa(job #3318140)

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

const int NMAX = 10000005;
const long long BASE = 131;
const long long MOD = 1000000007;
const char HASHER = 'a' - 1;

char A[NMAX], B[25];
long long powers[25];

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

void PrecomputePowers(int n) {
    powers[0] = 1;
    for (int i = 1; i <= n; i++)
        powers[i] = (powers[i - 1] * BASE) % MOD;
}

long long HashEntireString(const char s[], int n) {
    long long h = 0;
    for (int i = 0; i < n; i++)
        h = (h * BASE + (s[i] - HASHER)) % MOD;
    return h;
}

int RabinKarp(const char pattern[], const char text[]) {
    int n = strlen(pattern);
    int m = strlen(text);
    if (n > m) return 0;

    long long hash_pattern = HashEntireString(pattern, n);
    long long hash_text = HashEntireString(text, n);
    int count = 0;

    if (hash_pattern == hash_text) count++;

    for (int i = n; i < m; i++) {
        hash_text = (hash_text - (text[i - n] - HASHER) * powers[n - 1]) % MOD;
        if (hash_text < 0) hash_text += MOD;
        hash_text = (hash_text * BASE + (text[i] - HASHER)) % MOD;
        if (hash_text == hash_pattern) count++;
    }

    return count;
}

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;
        return 0;
    }

    int L = cuvinte[0].size();
    PrecomputePowers(L);


    unordered_set<string> unice;
    for (auto &w : cuvinte)
        if ((int)w.size() == L)
            unice.insert(w);

    long long total = 0;

    for (auto &cuv : unice)
        total += RabinKarp(cuv.c_str(), A);

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