Cod sursa(job #3278085)

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

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

const int SIZE = 25;
const uint64_t base = 269696969;

int word_len;
std::string text, word;
uint64_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() 
{

    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[text_hash])
            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[text_hash])
            count++;
    }

    fout << count;
    
    return 0;
}