Cod sursa(job #2678239)

Utilizator George_CristianGeorge Dan-Cristian George_Cristian Data 28 noiembrie 2020 11:20:21
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.58 kb
#include <cstdio>
#include <cstring>

#define MAXN 2000005

#define D 73
#define MOD1 100007
#define MOD2 100021

char a[MAXN], b[MAXN];
int nrla, nrlb, hashA1, hashA2, P1 = 1, P2 = 1, hash1, hash2, nr_pot;
bool match[MAXN];

void citire() {
    freopen("strmatch.in", "r", stdin);
    freopen("strmatch.out", "w", stdout);
    scanf("%s\n%s", a, b);
    nrla = strlen(a);
    nrlb = strlen(b);
}

void initializare() {
    for (int i = 0; i < nrla; ++i) {
        hashA1 = (hashA1 * D + a[i]) % MOD1;
        hashA2 = (hashA2 * D + a[i]) % MOD2;

        if (i != 0) {
            P1 = (P1 * D) % MOD1;
            P2 = (P2 * D) % MOD2;
        }
    }

    for (int i = 0; i < nrla; ++i) {
        hash1 = (hash1 * D + b[i]) % MOD1;
        hash2 = (hash2 * D + b[i]) % MOD2;
    }
}

void cautare_potriviri() {
    if (hash1 == hashA1 && hash2 == hashA2) {
        match[0] = true;
        nr_pot++;
    }

    for (int i = nrla; i < nrlb; ++i) {
        hash1 = ((hash1 - (b[i - nrla] * P1) % MOD1 + MOD1) * D + b[i]) % MOD1;
        hash2 = ((hash2 - (b[i - nrla] * P2) % MOD2 + MOD2) * D + b[i]) % MOD2;

        if (hash1 == hashA1 && hash2 == hashA2) {
            match[i - nrla + 1] = true;
            nr_pot++;
        }
    }
}

void afisare() {
    printf("%d\n", nr_pot);
    nr_pot = 0;
    for (int i = 0; i < nrlb && nr_pot < 1000; ++i)
        if (match[i]) {
            nr_pot++;
            printf("%d ", i);
        }
}

int main() {
    citire();
    if (nrla > nrlb) {
        printf("0");
        return 0;
    }
    initializare();
    cautare_potriviri();
    afisare();
    return 0;
}