Cod sursa(job #2465973)

Utilizator Bulboaca_EugenBulboaca Alexandru Eugen Bulboaca_Eugen Data 1 octombrie 2019 09:47:37
Problema Potrivirea sirurilor Scor 14
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.45 kb
#include <bits/stdc++.h>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
const int MAXN = 2 * 1e5 + 5;
const int MOD1 = 666013;
const int MOD2 = 666019;
const int baza = 73;
string a, b;
vector <int> ans;
int hasha1, hasha2;
int hashb1[MAXN], hashb2[MAXN];
int na, nb, p1, p2, cnt, putere1[MAXN], putere2[MAXN];
int main()
{
    fin >> a >> b;
    na = a.size();
    nb = b.size();
    if(na > nb) {
        fout << "0";
        return 0;
    }
    for(int i = 0; i < na; ++i){
        hasha1 = (hasha1 * baza + a[i]) % MOD1;
        hasha2 = (hasha2 * baza + a[i]) % MOD2;
        (!i) ? putere1[0] = 1 : putere1[i] = putere1[i - 1] * baza % MOD1;
        (!i) ? putere2[0] = 1 : putere2[i] = putere2[i - 1] * baza % MOD1;
    }
    hashb1[0] = b[0], hashb2[0] = b[0];
    for(int i = 1; i < nb; ++i){
        hashb1[i] = (hashb1[i - 1] * baza + b[i]) % MOD1;
        hashb2[i] = (hashb2[i - 1] * baza + b[i]) % MOD2;
    }
    for(int i = 0; i < nb - na + 1; ++i){
        int r = i + na - 1, l = i;
        int hb1 = (hashb1[r] - (hashb1[l] * putere1[r - l] ) % MOD1 + MOD1) % MOD1;
        int hb2 = (hashb2[r] - (hashb1[l] * putere2[r - l] ) % MOD2 + MOD2) % MOD2;
        if(hb1 == hasha1 and hb2 == hasha2)
            cnt ++, ans.push_back(r);
    }
    fout << cnt << '\n';
    cnt = 0;
    for(auto x : ans){
        fout << x << " ", cnt++;
        if(cnt > 1000) break;
    }
    return 0;
}