Cod sursa(job #2791504)

Utilizator domistnSatnoianu Dominic Ioan domistn Data 30 octombrie 2021 16:01:29
Problema Potrivirea sirurilor Scor 60
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.55 kb
#include <cstdio>
#include <cstring>

#define NMAX 2000005

char s[NMAX], micut[NMAX];
int sl, micutl, ansl, ans[1005];

/*struct Hash {
    long long n = 71, m = 0, power = 0, value = 0, sl, i;
    char * s;
{1}
    Hash(char * X, const int XL, const int M) {
        s = X;
        sl = XL;
        i = sl;
        m = M;
        power = 1;
        value = 0;
        for(int i = sl - 1; i >= 0; --i) {
            value = (value + power * s[i] % m) % m;
            if(i) power = power * n % m;
        }
    }
{1}
    void roll() {
        value = (((value - power * s[i - sl] % m + m) % m * n) % m + s[i]) % m;
        ++i;
    }
};*/

struct Hash {
private:
    long long n, d, p, put, val, poz;
    char *str;
public:
    Hash(int nn, int pp, char *strr) {
        n = nn;
        p = pp;
        d = 71;
        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", &micut);
    scanf("%s", &s);
    micutl = strlen(micut);
    sl = strlen(s);
}

void cautare() {
    /*Hash mh1 = Hash(micut, micutl, 100007),
         mh2 = Hash(micut, micutl, 100007),
         sh1 = Hash(s,     micutl, 100021),
         sh2 = Hash(s,     micutl, 100021);*/
    Hash mh1 = Hash(micutl, 100007, micut);
    Hash sh1 = Hash(micutl, 100007, s);
    Hash mh2 = Hash(micutl, 100021, micut);
    Hash sh2 = Hash(micutl, 100021, s);

    mh1.init();
    sh1.init();
    mh2.init();
    sh2.init();

    for(int i = 0; i < sl - micutl + 1; ++i) {
        //if(sh1.value == mh1.value && sh2.value == mh2.value) {
        if(sh1.get_val() == mh1.get_val() && sh2.get_val() == mh2.get_val()) {
            ++ansl;
            if(ansl <= 1000) ans[ansl] = i;
        }
        sh1.roll();
        sh2.roll();
    }
}

void afisare() {
    printf("%d\n", ansl);
    int poz = (ansl >= 1000 ? 1000 : ansl);
    for(int i = 1; i <= poz; ++i)
        printf("%d ", ans[i]);
}

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