Cod sursa(job #2787384)

Utilizator George_CristianGeorge Dan-Cristian George_Cristian Data 23 octombrie 2021 10:31:39
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.66 kb
#include <fstream>
#include <cstring>

using namespace std;

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

#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() {
    f >> a >> 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() {
    g << nrrez << '\n';
    int poz = min(nrrez, 1000);
    for (int i = 1; i <= poz; ++i)
        g << pozrez[i] << ' ';
}

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