Cod sursa(job #860617)

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

using namespace std;

#define Nmax  2000003

char P[Nmax], T[Nmax];
int L[Nmax], V[2024];
int n, m;
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;
    int k = 0;

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

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

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

        L[p] = k;
    }
}

void KMP(){

    prefix();

    int 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];

            if(cont + 1 <= 1000)
                V[++cont] = t - m;
            else
                break;
        }
    }
}

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();
    KMP();
    afis();

    return 0;
}