Cod sursa(job #3195175)

Utilizator iulia_morariuIulia Morariu iulia_morariu Data 20 ianuarie 2024 10:55:57
Problema Potrivirea sirurilor Scor 74
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.26 kb
#include <iostream>
#include <string>
#include <fstream>
#include <vector>
#define int long long

long long Mod = 1000000007;
long long P = 1007;

using namespace std;

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

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    string a, b; fin >> a >> b;
    signed n = a.size(), m = b.size();

    //cout << "n = " << n << " m = " << m << endl;

    int pw[m];
    pw[0] = 1;
    for(int i = 1; i < m; i++){
        pw[i] = (pw[i - 1] * P) % Mod;
    }

    int hasha = 0;
    for(int i = 0; i < n; i++){
        hasha = (hasha + a[i] * pw[i]) % Mod;
    }

    int hashb[m];
    hashb[0] = b[0];
    for(int i = 0; i < m; i++){
        hashb[i] = (hashb[i - 1] + b[i] * pw[i]) % Mod;
    }

    signed cnt = 0;
    vector<signed> poz;
    for(int i = 0; i <= m - n; i++){
        int ch = 0;
        if(i == 0) ch = hashb[n - 1];
        else ch = (hashb[i + n - 1] - hashb[i - 1] + Mod) % Mod;

        //cout << "i = " << i << " ch = " << ch << " hasha = " << hasha << endl;

        if(ch == (hasha * pw[i]) % Mod){
            cnt++;
            poz.push_back(i);
        }
    }

    fout << cnt << '\n';
    for(int i = 0; i < min(cnt, 1000); i++) fout << poz[i] << " ";
    fout << '\n';

    return 0;
}