Cod sursa(job #2976348)

Utilizator Vlad_NistorNIstor Vlad Vlad_Nistor Data 8 februarie 2023 23:16:27
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.62 kb
#include <bits/stdc++.h>
using namespace std;
#define base 97
#define MOD 918723
#define MOD1 918423
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 ha1 = 0;
    int pw = 1, pw1 = 1;
    for(int i = 0;i<na;i++){
        ha = (ha * base + a[i]) % MOD;
        ha1 = (ha1 * base + a[i]) % MOD1;
        if(i > 0){
            /// calculam puterile
            pw *= base;
            pw %= MOD;
            pw1 *= base;
            pw1 %= MOD1;
        }
    }
    /// 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, hb1 = 0, ans = 0;
    for(int i = 0;i<na;i++){
        hb = (hb * base + b[i]) % MOD;
        hb1 = (hb1 * base + b[i]) % MOD1;
    }
    if(ha == hb && ha1 == hb1){
        sol.push_back(0); /// avem seventa matchy din prima
    }
    for(int i = na;i<nb;i++){
        /// acum ne "rostogolim"
        hb = ((hb - ((b[i - na] * pw)) % MOD + MOD) * base + b[i])% MOD;  /// poate fi negativ
        hb1 = ((hb1 - ((b[i - na] * pw1)) % MOD1 + MOD1) * base + b[i])% MOD1;
        if(hb == ha && ha1 == hb1){
            if(sol.size() < 1000)
                sol.push_back(i-na+1);
        }
    }
    cout << sol.size() << '\n';
    for(auto x: sol){
        cout << x << ' ';
    }
}