Cod sursa(job #3293406)

Utilizator petru-robuRobu Petru petru-robu Data 11 aprilie 2025 17:06:14
Problema Potrivirea sirurilor Scor 38
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.32 kb
#include <bits/stdc++.h>
#define ll long long
using namespace std;

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

const int p = 67;
const ll m = 1e9 + 9;

vector<ll> p_pow;
string pattern, str;
int pattern_size, str_size;

void compute_powers()
{
    ll pp = 1;
    for(int i=0; i<=str_size; i++)
    {
        p_pow.push_back(pp);
        pp = (pp*p) % m;
    }
}

ll compute_hash(string s)
{
    ll hash_val = 0;

    for(int i=0; i<s.size(); i++)
        hash_val = (hash_val + (s[i]-'0'+1) * p_pow[i]) % m;

    return hash_val;
}

int main()
{   
    fin >> pattern >> str;
    pattern_size = pattern.size();
    str_size = str.size();

    compute_powers();

    ll pattern_hash = 0;
    for(int i=0; i<pattern_size; i++)
        pattern_hash = (pattern_hash + (pattern[i] - '0' + 1)*p_pow[i]) % m;

    vector<ll> pref_hash(str_size+1, 0);
    for(int i=0; i<str_size; i++)
    {
        pref_hash[i+1] = (pref_hash[i] + (str[i] - '0' + 1) * p_pow[i]) % m;
    }

    vector<int> occurences;

    for(int i=0; i<str_size - pattern_size; i++)
    {
        ll curr_hash = (pref_hash[i + pattern_size]  + m - pref_hash[i]) % m;
        if(curr_hash == pattern_hash * p_pow[i] % m)
            occurences.push_back(i);
    }

    fout<<occurences.size()<<'\n';
    for(auto &idx: occurences)
        fout<<idx<<' ';
    

    return 0;
}