Cod sursa(job #3318150)

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

const int HASH_BASE = 3;
string text;
string word;
unordered_set<unsigned int> wordHashes;


unsigned int computeHash(const string &word) {
    unsigned int hashValue = 0;
    for (char c : word) {
        hashValue = hashValue * HASH_BASE + (c - 'a');
    }
    return hashValue;
}


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

int main() {
    ifstream inputFile("abc2.in");
    ofstream outputFile("abc2.out");

    inputFile >> text;

    while (inputFile >> word) {
        wordHashes.insert(computeHash(word));
    }

    int wordLength = word.size();
    unsigned int currentHash = 0;
    unsigned int highestPow = powUnsigned(HASH_BASE, wordLength - 1);
    int matchCount = 0;

    for (int i = 0; i < text.size(); ++i) {
        currentHash = currentHash * HASH_BASE + (text[i] - 'a');

        if (i >= wordLength - 1) {
            if (wordHashes.find(currentHash) != wordHashes.end()) {
                ++matchCount;
            }

            currentHash -= highestPow * (text[i - (wordLength - 1)] - 'a');
        }
    }

    outputFile << matchCount;
}