Cod sursa(job #148431)

Utilizator bogdanhm999Casu-Pop Bogdan bogdanhm999 Data 4 martie 2008 12:32:13
Problema Potrivirea sirurilor Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.86 kb
#include <stdio.h>
#include <string.h>
#define nMax 2000005

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

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

int main(){
    freopen("strmatch.in","r",stdin);
    freopen("strmatch.out","w",stdout);
    
    int i,x=-1;
    
    scanf("%s",B);
    scanf("%s",A);
    
    n=strlen(A);
    m=strlen(B);
    
    urmatorul();
    
    for (i=0;i<n;i++){
        while (x>0&&B[x+1]!=A[i])x=urm[x];
        if (B[x+1]==A[i])x++;
        if (x==m-1){//solutie
           x=urm[x];
           sol++;
           v[sol]=i-m+1;
        }
    }
    printf("%ld\n",sol);
    for (i=1;i<=sol;i++)
        printf("%ld ",v[i]);
    printf("\n");

return 0;
}