Cod sursa(job #2976316)

Utilizator Vlad_NistorNIstor Vlad Vlad_Nistor Data 8 februarie 2023 22:22:18
Problema Potrivirea sirurilor Scor 34
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.34 kb
#include <bits/stdc++.h>
using namespace std;
#define base 26
#define MOD 918723

vector<int> sol;
int main(void){
    ofstream cout("strmatch.out");
    ifstream cin("strmatch.in");
    string a,b;
    cin >> a >> b;
    int na = a.size();
    int nb = b.size();
    if(na > nb){
        cout << 0;
        return 0;
    }
    /// prima data vom calcula hashul pentru a (pattern-ul)
    int ha = 0; /// hashul lui a
    int pw = 1;
    for(int i = 0;i<na;i++){
        ha = (ha * base + a[i]) % MOD;
        if(i > 0){
            /// calculam puterile
            pw *= base;
            pw %= MOD;
        }
    }
    /// dupa ce am obtinut hash-ul pentru pattern trebuie obtinut si pentru prima secventa de lungimen na apoi ne "rostogolim" prin celelalte secv
    int hb = 0, ans = 0;
    for(int i = 0;i<na;i++){
        hb = (hb * base + b[i]) % MOD;
    }
    if(ha == hb){
        sol.push_back(1); /// avem seventa matchy din prima
    }
    for(int i = na;i<nb;i++){
        /// acum ne "rostogolim"
        hb = (base * (hb - b[i - na] * pw) + b[i]) % MOD;
        if(hb < 0){
            hb += MOD;
        }
        if(hb == ha){
            if(sol.size() < 1000)
                sol.push_back(i-na+1);
        }
    }
    cout << sol.size() << '\n';
    for(auto x: sol){
        cout << x << ' ';
    }
}