Cod sursa(job #2791133)

Utilizator George_CristianGeorge Dan-Cristian George_Cristian Data 30 octombrie 2021 09:52:13
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.04 kb
#include <cstdio>
#include <cstring>

#define NMAX 2000005

char a[NMAX], b[NMAX];
int nrla, nrlb, p[NMAX], nrrez, pozrez[1005];

void citire() {
    scanf("%s", &a);
    scanf("%s", &b);
    nrla = strlen(a);
    nrlb = strlen(b);
}

void formare_prefixe() {
    p[0] = -1;
    for (int i = 0, j = -1; i < nrla; ++i) {
        while (j >= 0 && a[i] != a[j])
            j = p[j];
        j++;
        p[i + 1] = j;
    }
}

void kmp() {
    int j = 0;
    for (int i = 0; i < nrlb; ++i) {
        while (j >= 0 && b[i] != a[j])
            j = p[j];
        j++;
        if (j == nrla) {
            j = p[j];
            nrrez++;
            if (nrrez <= 1000)
                pozrez[nrrez] = i - nrla + 1;
        }
    }
}

void afisare() {
    printf("%d\n", nrrez);
    int limita = (nrrez < 1000) ? nrrez : 1000;
    for (int i = 1; i <= limita; ++i)
        printf("%d ", pozrez[i]);
}

int main() {
    freopen("strmatch.in", "r", stdin);
    freopen("strmatch.out", "w", stdout);
    citire();
    formare_prefixe();
    kmp();
    afisare();
    return 0;
}