Cod sursa(job #2195923)

Utilizator Constantin.Dragancea Constantin Constantin. Data 17 aprilie 2018 19:50:47
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.11 kb
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int MOD1 = 1e6 + 3;
const int MOD2 = 1e6 + 33;
const int prime = 71;
int hasha1, hasha2, hashb1, hashb2, put1 = 1, put2 = 1;
string a, b;
vector <int> sol;

int main(){
    ifstream cin ("strmatch.in");
    ofstream cout ("strmatch.out");
    cin >> a >> b;
    int n = a.length(), m = b.length();
    for (int i=0; i<a.length(); i++){
        hasha1 = (hasha1 * prime + a[i]) % MOD1;
        hasha2 = (hasha2 * prime + a[i]) % MOD2;

        hashb1 = (hashb1 * prime + b[i]) % MOD1;
        hashb2 = (hashb2 * prime + b[i]) % MOD2;

        if (!i) continue;
        put1 = (put1 * prime) %MOD1;
        put2 = (put2 * prime) %MOD2;
    }
    for (int i=0; i<=m-n; i++){
        if (hasha1 == hashb1 && hasha2 == hashb2) sol.push_back(i);

        hashb1 = ((hashb1 - (b[i] * put1)%MOD1 + MOD1)*prime + b[i+n])%MOD1;
        hashb2 = ((hashb2 - (b[i] * put2)%MOD2 + MOD2)*prime + b[i+n])%MOD2;
    }
    cout << sol.size() << "\n";
    for (int i=0; i<min(1000,int (sol.size())); i++) cout << sol[i] << " ";
    return 0;
}