Cod sursa(job #2791131)

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

using namespace std;

const int NMAX = 2000003;

int sl, micutl, ans[1010], ansl;
char s[NMAX + 1], micut[NMAX + 1];

class Hash {
    private:
        long long n = 97, m = 666013, power = 0;
    public:
        long long value = 0;

        Hash() {
            power = value = 0;
        }

        void init(const char * X, const int XL, const int M) {
            m = M;
            power = 1;
            value = 0;
            for(int i = XL; i; --i) {
                value = (value + power * X[i] % m) % m;
                if(i - 1) power = power * n % m;
            }
        }

        void roll(const char toRem, const char toAdd) {
            value = (((value - (1ll * toRem * power) % m + m) * n) % m + toAdd) % m;
        }
};

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

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

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

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