Cod sursa(job #2710426)

Utilizator George_CristianGeorge Dan-Cristian George_Cristian Data 22 februarie 2021 16:14:20
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.5 kb
#include <fstream>
#include <cstring>

using namespace std;

ifstream f("strmatch.in");
ofstream g("strmatch.out");

#define d 72
#define MOD1 100007
#define MOD2 100021
#define LGMAX 2000005

char a[LGMAX], b[LGMAX];
int nr, nrla, nrlb, hasha1, hash1, hasha2, hash2, p1 = 1, p2 = 1;
bool potr[LGMAX];

void citire() {
    f >> a >> b;
    nrla = strlen(a);
    nrlb = strlen(b);
}

void creare_hash(int i) {
    hasha1 = (hasha1 * d + a[i]) % MOD1;
    hasha2 = (hasha2 * d + a[i]) % MOD2;
    hash1 = (hash1 * d + b[i]) % MOD1;
    hash2 = (hash2 * d + b[i]) % MOD2;
}

void initializare_hash() {
    creare_hash(0);
    for (int i = 1; i < nrla; ++i) {
        creare_hash(i);
        p1 = (p1 * d) % MOD1;
        p2 = (p2 * d) % MOD2;
    }
}

void gasire_potriviri() {
    if (hash1 == hasha1 && hash2 == hasha2) {
        potr[0] = true;
        nr++;
    }
    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) {
            potr[i - nrla + 1] = true;
            nr++;
        }
    }
}

void afisare() {
    g << nr << '\n';
    nr = 0;
    for (int i = 0; i < nrlb && nr < 1000; ++i)
        if (potr[i]) {
            g << i << ' ';
            nr++;
        }
}

int main() {
    citire();
    if (nrla > nrlb) {
        g << 0;
        return 0;
    }
    initializare_hash();
    gasire_potriviri();
    afisare();
    return 0;
}