Cod sursa(job #2969251)

Utilizator LucaT2Tasadan Luca LucaT2 Data 22 ianuarie 2023 19:16:30
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.36 kb
#include <bits/stdc++.h>
using namespace std;
#define ull unsigned long long
#define M 1000000007
#define p 31
#define MAX_LEN 2000001

ifstream fin("strmatch.in");
ofstream fout("strmatch.out");

char a[MAX_LEN], b[MAX_LEN];
int sol[MAX_LEN];
int n;

void citire() {
    fin >> a;
    fin.get();
    fin >> b;
}

ull get_hash(char* s, int len) {
    ull h = 0;
    for (int i = 0; i < len; i++) {
        h = (h * p + s[i]) % M;
    }
    return h;
}

ull get_pow(int len) {
    ull res = 1;
    for (int i = 0; i < len; i++) {
        res = (res * p) % M;
    }
    return res;
}

void rabinkarp() {
    int la = strlen(a);
    int lb = strlen(b);

    if (la > lb) {
        fout << 0;
        return;
    }

    ull ha = get_hash(a, la);
    ull hb = get_hash(b, la);
    ull pow = get_pow(la - 1);

    if (ha == hb) {
        sol[0] = 1;
        n++;
    }

    for (int i = la; i < lb; i++) {
        hb = ((hb - b[i - la] * pow % M) + M) % M;
        hb = (hb * p + b[i]) % M;

        if (hb == ha) {
            sol[i - la + 1] = 1;
            n++;
        }
    }

    fout << n << endl;
    n = 0;
    for (int i = 0; i < lb && n < 1000; i++) {
        if (sol[i]) {
            fout << i << " ";
            n++;
        }
    }
}

int main() {
    citire();
    rabinkarp();
    return 0;
}