Cod sursa(job #2791392)

Utilizator domistnSatnoianu Dominic Ioan domistn Data 30 octombrie 2021 13:59:39
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.49 kb
#include <iostream>
#include <cstring>

using namespace std;

const int NMAX = 2000000;

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

struct Hash {
    long long n = 97, m = 0, power = 0, value = 0, sl, i;
    char * s;

    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;
        }
    }

    void roll() {
        value = (((value - (1ll * s[i - sl] * power) % m + m) * n) % m + s[i]) % m;
        ++i;
    }
};

int main()
{
    freopen("strmatch.in", "r", stdin);
    freopen("strmatch.out", "w", stdout);
    scanf("%s %s", micut, s);
    micutl = strlen(micut), sl = strlen(s);

    if(micutl > sl) {
        printf("0");
        return 0;
    }

    Hash mh1 = Hash(micut, micutl, 100003),
         mh2 = Hash(micut, micutl, 100019),
         sh1 = Hash(s, micutl, 100003),
         sh2 = Hash(s, micutl, 100019);

    for(int i = micutl - 1; i < sl; ++i) {
        if(sh1.value == mh1.value && sh2.value == mh2.value) {
            ++ansl;
            if(ansl <= 1000) ans[ansl] = i - micutl + 1;
        }
        sh1.roll(),
        sh2.roll();
    }
    printf("%d\n", ansl);
    ansl = min(ansl, 1000);
    for(int i = 1; i <= ansl; ++i) {
        printf("%d ", ans[i]);
    }
    return 0;
}