Cod sursa(job #186929)

Utilizator drag0shSandulescu Dragos drag0sh Data 29 aprilie 2008 08:39:56
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 0.88 kb
#include <stdio.h>
#include <string.h>
#define MAX 2000001
char a[MAX],b[MAX];
int urm[MAX],n,m;
void urmatorul(){
    long k,x;
    k=-1;
    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);
  gets(b); gets(a);
    n=strlen(a);
    m=strlen(b);
    long v[1001],x,i;
    urmatorul();
    int c;
    c=0;
    x=-1;
    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){
            if(c<1000) v[++c]=i-m+1;
            else c++;
            x=urm[x];
        }
    }
    printf("%d\n",c);
    if(c>1000)c=1000;
    for(i=1;i<=c;i++)printf("%ld ",v[i]);


//    printf("%s",b);

    fclose(stdin);
    fclose(stdout);
return 0;
}