Cod sursa(job #662538)

Utilizator vendettaSalajan Razvan vendetta Data 16 ianuarie 2012 19:49:27
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.58 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(){

    //sirurile sunt indexate de la 1 la length( P )/( T ) +1

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

}

void urmatorul(){

    urm[1] = 0;

    int q = 0;

    for(int i=2; i<=m; ++i){//determin cel mai mare prefix din P care e sufix pentru sirul P[1..q]
        while( q>0 && P[q+1] != P[i]) q = urm[q];//cat timp nu gasesc un sir pe care sa`l pot continua ma duc mai departe
        if (P[q+1] == P[i]) ++q;//daca urmatoare potrivire e corecta o continui
        urm[i] = q;//salvez lungimea
    }

}

void rezolva(){

    int q=0;

    urmatorul();

    for(int i=1; i<=n; ++i){
        while( q>0 && P[q+1] != T[i]) q = urm[q];//cat timp nu se potrivesc pozitiile P[q+1] , T[i] sar la urmatoare pozitie
        if (P[q+1] == T[i]) ++q;//daca urmatoarea potrivire e corecta o continui
        if (q == m){//daca am gasit o aparitie o salvez
            Sol[ ++Sol[0] ] = i-m;
            q = urm[q];//sar la urmatoarea pozitie
        }
    }

}

void scrie(){

    //afisez doar primele 1000 aparitii

    if (Sol[0] > 1000) Sol[0] = 1000;

    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;

}