Cod sursa(job #860596)

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

using namespace std;

static const int Nmax = 2000002;

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

void citire(){

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

    char c;

    while(c!='\n')
        scanf("%c", &c),
        P[++m] = c;

    c = ' ';

    while(c!='\n')
        scanf("%c", &c),
        T[++n] = c;

    m--;
    n--;
}

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

            V[++cont] = t - m;
            k = L[k];
        }
    }
}

void afis(){

    freopen("stramatch.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;
}