Cod sursa(job #3277931)

Utilizator jumaracosminJumara Cosmin-Mihai jumaracosmin Data 18 februarie 2025 09:12:45
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.52 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;
int64_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) % mod;
}

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';
        pattern_hash %= mod;
    }
    
    for(int i = 0; i < text_len; ++i)
    {
        text_hash[i + 1] = text_hash[i] * base;
        text_hash[i + 1] += text[i] - '0';
        text_hash[i + 1] %= mod;
    }

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

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