Cod sursa(job #1251590)

Utilizator OnimushaLordTiberiu Copaciu OnimushaLord Data 29 octombrie 2014 18:09:14
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.02 kb
# include <cstring>
# include <cstdio>

#define MAXN 2000003

char X[MAXN], Y[MAXN];
int Pi[MAXN], d[MAXN];
int i, K, N, M;
int nr;

void constructie_pi()
{
    N = strlen(X)-1;
    K = 0;
    Pi[1] = 0;
    for (i = 2; i <= N; ++i)
    {
        while (K > 0 && X[i] != X[K+1])
            K = Pi[K];
        if (X[i] == X[K+1]) K = K + 1;
        Pi[i] = K;
    }
}

int main()
{
    freopen("strmatch.in","r",stdin);
    freopen("strmatch.out","w",stdout);

    fgets(X+1, MAXN, stdin);
    fgets(Y+1, MAXN, stdin);
    X[0] = ' ';
    Y[0] = ' ';
    X[strlen(X)-1] = Y[strlen(Y)-1] = 0;

    M = strlen(Y)-1;
    constructie_pi();
    K = 0;
    for (i = 1; i <= M; ++i)
    {
        while (K > 0 && Y[i] != X[K+1])
            K = Pi[K];
        if (Y[i] == X[K+1]) K = K + 1;
        d[i] = K;
    }
    for (i = 1;  i <= M; ++i)
        if (d[i] == N) nr++;
    printf("%d\n", nr);
    for (i = 1;  i <= M; ++i)
        if (d[i] == N)
            printf("%d ", i-N);
    return 0;
}