Cod sursa(job #2976376)

Utilizator divadddDavid Curca divaddd Data 9 februarie 2023 00:37:43
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2 kb
#include <bits/stdc++.h>
using namespace std;
#define int long long int
#define base 69
#define MOD  100005
#define MOD1 321307
vector<int> sol;

signed 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
       /*
        hb -= (b[i-na] * pw) % MOD;
        if(hb < 0){
            hb += MOD;
        }
        hb *= base;
        hb += b[i];
        hb %= MOD;
        */
        hb1 = ((hb1 - (b[i - na] * pw1) % MOD1 + MOD1) * base + b[i])% MOD1;

       /*
        hb1 -= (b[i-na] * pw1) % MOD1;
        if(hb1 < 0){
            hb += MOD1;
        }
        hb1 *= base;
        hb1 += b[i];
        hb1 %= 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 << ' ';
    }
}