Cod sursa(job #148481)

Utilizator bogdanhm999Casu-Pop Bogdan bogdanhm999 Data 4 martie 2008 13:26:43
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.96 kb
#include <stdio.h>
#include <string.h>
#define nMax 2000005
#define minim(a, b) ((a < b) ? a : b)

long n,m,sol=0,v[1024];
long urm[nMax];
char A[nMax],B[nMax];

void urmatorul(){
     int k=0,i;
     urm[1]=0;
     for (i=2;i<=m;i++){
         while (k>0&&B[k+1]!=B[i])k=urm[k];
         if (B[k+1]==B[i])k++;
         urm[i]=k;
     }
}

int main(){
    freopen("strmatch.in","r",stdin);
    freopen("strmatch.out","w",stdout);
    
    int i,x=0;
    
    scanf("%s",B+1);
    scanf("%s",A+1);
    
    n=strlen(A+1);
    m=strlen(B+1);

    urmatorul();
    
    for (i=1;i<=n;i++){
        while (x>0&&B[x+1]!=A[i])x=urm[x];
        if (B[x+1]==A[i])x++;
        if (x==m){//solutie
           x=urm[x];
           sol++;
           if (sol<=1000)
              v[sol]=i-m;
        }
        
    }
    
    printf("%ld\n",sol);
    for (i=1;i<=minim(sol,1000);i++)
        printf("%ld ",v[i]);
    printf("\n");

return 0;
}