Cod sursa(job #3200406)

Utilizator Mihai_PopescuMihai Popescu Mihai_Popescu Data 4 februarie 2024 16:37:56
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.36 kb
#include <fstream>
#include <cstring>
using namespace std;

ifstream fin("strmatch.in");
ofstream fout("strmatch.out");

#define NMAX 2000005

#define MOD1 666013
#define MOD2 1000007

#define b1 101
#define b2 103

char a[NMAX], b[NMAX];
int rez[1005];

int main() {
    fin >> a >> b;
    int l1 = strlen(a), l2 = strlen(b);
    int h1 = 0, h2 = 0;
    for (int i = 0; i < l1; ++i) {
        h1 = (h1 * b1 + a[i]) % MOD1;
        h2 = (h2 * b2 + a[i]) % MOD2;
    }

    int hash1 = 0, hash2 = 0;
    int putere1 = 1, putere2 = 1;
    for (int i = 0; i < l1; ++i) {
        hash1 = (hash1 * b1 + b[i]) % MOD1;
        hash2 = (hash2 * b2 + b[i]) % MOD2;
        if (i != 0) {
            putere1 *= b1;
            putere2 *= b2;

            putere1 %= MOD1;
            putere2 %= MOD2;
        }
    }
    int cnt = 0;
    if (h1 == hash1 && h2 == hash2) {
        rez[++cnt] = 0;
    }
    for (int i = l1; i < l2; ++i) {
        hash1 = ((hash1 - b[i - l1] * putere1 % MOD1 + MOD1) % MOD1 * b1 + b[i]) % MOD1;
        hash2 = ((hash2 - b[i - l1] * putere2 % MOD2 + MOD2) % MOD2 * b2 + b[i]) % MOD2;

        if (h1 == hash1 && h2 == hash2 && cnt < 1000) {
            rez[++cnt] = i - l1 + 1;
        }
    }

    fout << cnt << '\n';
    for (int i = 1; i <= cnt; ++i) {
        fout << rez[i] << ' ';
    }
    return 0;
}