Cod sursa(job #1685725)

Utilizator rughibemBelcineanu Alexandru Ioan rughibem Data 11 aprilie 2016 20:21:30
Problema Potrivirea sirurilor Scor 80
Compilator cpp Status done
Runda Arhiva educationala Marime 1.02 kb
#include<cstdio>
#include<cstring>
#define DIM 2000016
FILE *f=fopen("strmatch.in","r"), *g=fopen("strmatch.out","w");

char A[DIM], B[DIM];
int N, M, SOL[1005], lSOL = 0, P[DIM];

void Citire(){

    fscanf(f,"%s\n",A+1);
    fscanf(f,"%s\n",B+1);

    N = strlen(A+1);
    M = strlen(B+1);

}

void Rezolvare(){
int i, L;

    P[1] = L = 0;

    for(i=2;i<=N;i++){

        while( A[i] != A[L+1] && L > 0 )
            L = P[L];

        if( A[i] == A[L+1] )
            L ++;

        P[i] = L;

    }

    L = 0;

    for(i=1;i<=M;i++){

        while( ( B[i] != A[L+1] && L > 0 ) || L == N )
            L = P[L];

        if( B[i] == A[L+1] )
            L ++;

        if( L == N )
            SOL[++lSOL] = i-L;

    }

}

void Afisare(){
int i, k;

    fprintf(g,"%d\n",lSOL);

    k = lSOL;
    if( k > 1000 )
        k = 1000;

    for(i=1;i<=k;i++)
        fprintf(g,"%d ",SOL[i]);

}

int main(){

    Citire();
    Rezolvare();
    Afisare();

return 0;
}