Cod sursa(job #2131879)

Utilizator Constantin.Dragancea Constantin Constantin. Data 15 februarie 2018 08:37:35
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.06 kb
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

#define MOD 100007
#define prime 73
//puterile descresc de la stanga la dreapta

string a, b;
ll n, m, hasha, hashb, k, put = 1;
vector <int> sol;

int main(){
    ifstream cin ("strmatch.in");
    ofstream cout ("strmatch.out");
    cin >> a >> b;
    n = a.length();
    m = b.length();
    for (int i=0; i<n; i++){
        //hashuim primu string
        hasha = (hasha * prime + a[i])% MOD;

        //hashuim primele n caractere a sirului b
        hashb = (hashb * prime + b[i])% MOD;

        //calculam puterea max (m-1)
        if (i){
            put = (put * prime)% MOD;
        }
    }
    for (int i=0; i<=m-n; i++){
        if (hasha == hashb){
            k++;
            if (k <= 1000) sol.push_back(i);
        }

        //facem update hashului subsirului din b, x = x-char1*put + newcar
        hashb = ((hashb - (b[i] * put) % MOD + MOD) * prime + b[i+n])% MOD;
    }
    cout << k << "\n";
    for (auto it: sol) cout << it << " ";
    return 0;
}