Cod sursa(job #3278099)

Utilizator jumaracosminJumara Cosmin-Mihai jumaracosmin Data 18 februarie 2025 17:55:06
Problema Abc2 Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.42 kb
#include <bits/stdc++.h>

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

const int SIZE = 20;
const int64_t base = 269696969;

int word_len;
std::string text, word;
int64_t power[SIZE + 1];

std::unordered_map<uint64_t, bool> hash_words;

void precompute_powers()
{
    power[0] = 1;
    for(int i = 1; i <= SIZE; ++i)
        power[i] = power[i - 1] * base;
}

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

    fin >> text;

    precompute_powers();

    while(!fin.eof())
    {
        fin >> word;
        word_len = word.length();

        uint64_t pattern_hash = 0;
        for(int i = 0; i < word_len; ++i)
            pattern_hash = pattern_hash * base + (word[i] - 'a' + 1);

        hash_words[pattern_hash] = true;
    }

    if(text.length() < word_len)
    {
        fout << 0;
        return 0;
    }

    uint64_t text_hash = 0;
    for(int i = 0; i < word_len; ++i)
        text_hash = text_hash * base + (text[i] - 'a' + 1);

    int count = 0;
    if(hash_words.find(text_hash) != hash_words.end())
            count++;

    for(int i = word_len; i < text.length(); ++i)
    {
        text_hash = (text_hash - ((text[i - word_len] - 'a' + 1) * power[word_len - 1])) * base + (text[i] - 'a' + 1);

        if(hash_words.find(text_hash) != hash_words.end())
            count++;
    }

    fout << count;
    
    return 0;
}