Cod sursa(job #860609)

Utilizator AlexandruValeanuAlexandru Valeanu AlexandruValeanu Data 20 ianuarie 2013 14:22:17
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.15 kb
#include <iostream>
#include <cstring>
#include <cstdio>

using namespace std;

#define Nmax  2000002

char P[Nmax], T[Nmax];
int L[Nmax], V[2000];
int n, m;
int k;
int cont = 0;

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(){

    L[1] = 0;

    for(int p = 2; p <= m; p++){

        k = L[p-1];

        while(k > 0 && P[k+1] != P[p])
            k = L[k];

        if(P[k+1] == P[p])
            k++;

        L[p] = k;
    }
}

void KMP(){

    prefix();

    k = 0;

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

        while(k > 0 && P[k+1] != T[t])
            k = L[k];

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

        if(k == m)
            k = L[k],
            V[++cont] = t - m;
    }
}

void afis(){

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

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

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

int main()
{
    citire();
    KMP();
    afis();

    return 0;
}