Cod sursa(job #2391121)

Utilizator Constantin.Dragancea Constantin Constantin. Data 28 martie 2019 17:54:27
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.03 kb
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

#define mod1 1000003
#define mod2 1000033
#define p 73
string a, b;
ll ha1, ha2, hb1, hb2, put1 = 1, put2 = 1, cnt;
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<n; i++){
        ha1 = (ha1 * p + a[i])%mod1;
        ha2 = (ha2 * p + a[i])%mod2;

        hb1 = (hb1 * p + b[i])%mod1;
        hb2 = (hb2 * p + b[i])%mod2;
        if (!i) continue;
        put1 = (put1 * p)%mod1;
        put2 = (put2 * p)%mod2;
    }
    for (int i=0; i<=m-n; i++){
        if (ha1 == hb1 && ha2 == hb2){
            cnt++;
            if (cnt <= 1000) sol.push_back(i);
        }
        if (i == m-n) continue;
        hb1 = ((hb1 - (b[i]*put1)%mod1 + mod1)*p + b[i+n])%mod1;
        hb2 = ((hb2 - (b[i]*put2)%mod2 + mod2)*p + b[i+n])%mod2;
    }
    cout << cnt << '\n';
    for (auto it: sol) cout << it << ' ';
    return 0;
}