Cod sursa(job #793517)

Utilizator gallexdAlex Gabor gallexd Data 3 octombrie 2012 14:19:18
Problema Potrivirea sirurilor Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 0.89 kb
#include <cstdio>
#include <cstring>
#define L 2000010

char T[L],P[L];
int pi[L],poz[L];
int nr=0, M,N;

void prefix() {
    int k=0;
    for (int i=2; i<N; ++i) {
        while (k>1 && P[k+1]!=P[i])
            k = pi[k];
        if (P[k+1] == P[i]) ++k;
        pi[i] = k;
    }
}

void cauta () {
    int k=0;
    for (int i=1; i<M; ++i) {
        while (k>0 && T[i]!=P[k+1])
            k = pi[k];
        if (T[i]==P[k+1]) ++k;
        if (k==N-1) k=pi[k], poz[nr++] = i-N+1;
    }
}

void afisare() {
    printf("%d\n", nr);
    if (nr>1000) nr = 1000;
    for (int i=0; i<nr; ++i)
        printf("%d ", poz[i]);
}

int main () {

    freopen("strmatch.in","rt",stdin);
    freopen("strmatch.out","wt",stdout);

    fgets(P+1,L,stdin);
    fgets(T+1,L,stdin);
    M=strlen(T+1);
    N=strlen(P+1);
    prefix();
    cauta();
    afisare();

    return 0;
}