Cod sursa(job #3277932)

Utilizator jumaracosminJumara Cosmin-Mihai jumaracosmin Data 18 februarie 2025 09:14:30
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.44 kb
#include <bits/stdc++.h>

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

const int SIZE = 2e6;
const int base = 269696969;
const int mod = 1e9 + 7;
uint64_t text_hash[SIZE + 1], power[SIZE + 1];

std::string pattern, text;

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

int main() 
{
    
    fin >> pattern >> text;

    int text_len = text.length();
    int pattern_len = pattern.length();

    precompute_powers();

    uint64_t pattern_hash = 0;
    for(int i = 0; i < pattern_len; ++i)
    {
        pattern_hash *= base;
        pattern_hash += pattern[i] - '0';
    }
    
    for(int i = 0; i < text_len; ++i)
    {
        text_hash[i + 1] = text_hash[i] * base;
        text_hash[i + 1] += text[i] - '0';
    }

    int count = 0;
    std::vector<int> positions;
  
    for(int i = pattern_len; i <= text_len; ++i)
    {
        uint64_t full_hash = text_hash[i];
        uint64_t old_hash = text_hash[i - pattern_len];
        
        uint64_t curr_hash = (full_hash - (old_hash * power[pattern_len]));

        if(curr_hash == pattern_hash)
        {
            count++;
            if(count <= 1000)
                positions.emplace_back(i - pattern_len);
        }
    }
    
    fout << count << "\n";
    for(auto position : positions)
        fout << position << " ";
    
    return 0;
}