Cod sursa(job #1251598)

Utilizator OnimushaLordTiberiu Copaciu OnimushaLord Data 29 octombrie 2014 18:19:59
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.12 kb
# include <cstring>
# include <cstdio>
# include <algorithm>
#define min(a, b) ((a < b) ? a : b)

#define MAXN 2000003

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

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;
        if(d[i] == N)
        {
            n++;
            if(n <= 1000) pos[n]=i-N;
        }
    }
    printf("%d\n", n);
    for (i = 1;  i <= min(n, 1000); ++i)
        printf("%d ", pos[i]);
    return 0;
}