Cod sursa(job #3171125)

Utilizator Cyrex.1948Dumitrica Cezar Stefan Cyrex.1948 Data 18 noiembrie 2023 13:28:52
Problema Potrivirea sirurilor Scor 20
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.56 kb
#include <fstream>
#include <string>

using namespace std;

ifstream cin("strmatch.in");
ofstream cout("strmatch.out");

const int MAXN = 2000001;
const int BASE = 73;
const int MOD1 = 100007;
const int MOD2 = 100021;

string str, templ;
int N, M;

int hash1, hash2, pow1, pow2;

char match[MAXN];

int main() {
    cin >> str >> templ;
    N = str.size();
    M = templ.size();
    pow1 = pow2 = 1;
    hash1 = hash2 = 0;
    for (int i = 0; i < N; i++) {
        hash1 = (hash1 * BASE + str[i]) % MOD1;
        hash2 = (hash2 * BASE + str[i]) % MOD2;

        if (i != 0)
            pow1 = (pow1 * BASE) % MOD1,
            pow2 = (pow2 * BASE) % MOD2;
    }

    if (N > M) {
        cout << "0\n";
        return 0;
    }

    int hash1_clone = 0, hash2_clone = 0;

    for (int i = 0; i < N; i++){
        hash1_clone = (hash1_clone * BASE + templ[i]) % MOD1,
        hash2_clone = (hash2_clone * BASE + templ[i]) % MOD2;
    }
    int Nr = 0;
    if (hash1_clone == hash1 && hash2_clone == hash2)
        match[0] = 1, Nr++;
    for (int i = N; i < M; i++) {
        hash1_clone = ((hash1_clone - (templ[i - N] * pow1) % MOD1 + MOD1) * BASE + templ[i]) % MOD1;
        hash2_clone = ((hash2_clone - (templ[i - N] * pow2) % MOD2 + MOD2) * BASE + templ[i]) % MOD2;
        if (hash1_clone == hash1 && hash2_clone == hash2){
            match[i - N + 1] = 1;
            Nr++;
        }
    }
    cout << Nr << '\n';
    Nr = 0;
    for (int i = 0; i < N && Nr < 1000; i++){
        if (match[i]){
            Nr++;
            cout << i << ' ';
        }
    }
    cout << '\n';
    return 0;
}