Cod sursa(job #972822)

Utilizator CosminRusuCosmin Rusu CosminRusu Data 12 iulie 2013 18:35:43
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.23 kb
#include <cstdio>
#include <cstring>

#define Nmax 2000005

int m, n;
char P[Nmax], T[Nmax];
int L[Nmax], V[Nmax];
int cont;

void citire()
{

    freopen("strmatch.in", "r", stdin);

    fgets(P, sizeof(P), stdin);
    fgets(T, sizeof(T), stdin);

    m = strlen(P);
    n = strlen(T);

    for(int i = m; i > 0; i--)
        P[i] = P[i-1];

    for(int i = n; i > 0; i--)
        T[i] = T[i-1];
    n--;
    m--;
}

void prefix()
{

    int k = 0 ;

    for(int  i =2 ; i <= m ; ++ i)
    {
        while( k && P[k + 1] != P[i])
            k = L[k];
        if( P[k+1] == P[i])
            ++ k;
        L[i] = k;
    }
}

void KMP()
{

    int k = 0;

    for(int i = 1; i <= n; ++i)
    {

        while(k && P[k+1] != T[i])
            k = L[k];

        if(P[k+1] == T[i])
            k++;

        if(k == m)
        {
            k = L[m];
            V[++cont] = i-m;
        }
    }
}

void afis()
{

    freopen("strmatch.out", "w", stdout);

    printf("%d\n", cont);

    for(int i = 1; i <= (cont < 1000 ? cont : 1000); i++)
        printf("%d ", V[i]);

    printf("\n");
}

int main()
{

    citire();
    prefix();
    KMP();
    afis();

    return 0;
}