Cod sursa(job #662475)

Utilizator vendettaSalajan Razvan vendetta Data 16 ianuarie 2012 19:07:42
Problema Potrivirea sirurilor Scor 8
Compilator cpp Status done
Runda Arhiva educationala Marime 1.18 kb
#include <cstdio>
#include <cstring>
#define Nmax 2000005

using namespace std;

char P[Nmax], T[Nmax];
int n, m, urm[Nmax];
int Sol[Nmax];

void citeste(){

    scanf("%s", P);//citesc modelul ~pattern~
    scanf("%s", T);//citesc textul in care caut aparitiile
    m = strlen( P );
    n = strlen( T );
    --m; --n;
    //printf("%s\n", P);
    //printf("%s", T);

}

void urmatorul(){

    urm[0] = 0;
    int k = -1;

    for(int q=1; q<=m; ++q){//determin cel mai mare prefix din P care e sufix pentru sirul P[1..q]
        while( k>-1 && P[k+1] != P[q]) k = urm[k];
        if (P[k+1] == P[q]) ++k;
        urm[q] = k;
    }

}

void rezolva(){

    int k=-1;

    urmatorul();

    for(int q=0; q<=n; ++q){
        while( k>-1 && P[k+1] != T[q]) k = urm[k];
        if (P[k+1] == T[q]) ++k;
        if (k == m){
            Sol[ ++Sol[0] ] = q-m;
            k = urm[k];
        }
    }

}

void scrie(){

    printf("%d\n", Sol[0]);

    for(int i=1; i<=Sol[0]; ++i)
        printf("%d ",Sol[i]);

}

int main(){

    freopen("strmatch.in", "r", stdin);
    freopen("strmatch.out", "w", stdout);

    citeste();
    rezolva();
    scrie();

    fclose(stdin);
    fclose(stdout);

    return 0;

}