Cod sursa(job #2791110)

Utilizator George_CristianGeorge Dan-Cristian George_Cristian Data 30 octombrie 2021 09:28:12
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.75 kb
#include <cstdio>
#include <iostream>
#include <cstring>

using namespace std;

#define NMAX 2000005

char a[NMAX], b[NMAX];
int nrla, nrlb, nrrez, pozrez[1005];

class Hash {
private:
    long long n, d, p, put, val, poz;
    char *str;
public:
    Hash(int nn, int pp, int dd, char *strr) {
        n = nn;
        p = pp;
        d = dd;
        put = 1;
        val = 0;
        poz = 0;
        str = strr;
    }

    void init() {
        for (int i = n - 1; i >= 0; --i) {
            val = (val + (put * str[i]) % p) % p;
            if (i)
                put = (put * d) % p;
        }
    }

    void roll() {
        val = (((val - (put * str[poz]) % p + p) % p * d) % p + str[poz + n]) % p;
        poz++;
    }

    long long get_val() {
        return val;
    }
};

void citire() {
    scanf("%s", &a);
    scanf("%s", &b);
    nrla = strlen(a);
    nrlb = strlen(b);
}

void cautare() {
    Hash ha1 = Hash(nrla, 100007, 71, a);
    Hash hb1 = Hash(nrla, 100007, 71, b);
    Hash ha2 = Hash(nrla, 100021, 71, a);
    Hash hb2 = Hash(nrla, 100021, 71, b);

    ha1.init();
    hb1.init();
    ha2.init();
    hb2.init();

    for (int i = 0; i < nrlb - nrla + 1; ++i) {
        if (ha1.get_val() == hb1.get_val() && ha2.get_val() == hb2.get_val()) {
            nrrez++;
            if (nrrez <= 1000)
                pozrez[nrrez] = i;
        }
        hb1.roll();
        hb2.roll();
    }
}

void afisare() {
    printf("%d\n", nrrez);
    int poz = min(nrrez, 1000);
    for (int i = 1; i <= poz; ++i)
        printf("%d ", pozrez[i]);
}

int main() {
    freopen("strmatch.in", "r", stdin);
    freopen("strmatch.out", "w", stdout);
    citire();
    if (nrla > nrlb) {
        printf("%d", 0);
        return 0;
    }
    cautare();
    afisare();
    return 0;
}