Cod sursa(job #328223)

Utilizator tamas_iuliaTamas Iulia tamas_iulia Data 1 iulie 2009 12:50:15
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 0.83 kb
#include <stdio.h>
#include <string.h>
#define Nmax 2000005

char A[Nmax],B[Nmax];
long n,i,na,nb;
long v[1005],pi[Nmax];

void fa_prefix(){
	long k=-1,x;
   pi[0]=0;
   for(x=1;x<na;++x){
   	while(k>0 && A[k+1]!=A[x])
        k=pi[k];
      if(A[k+1]==A[x]) ++k;
      pi[x]=k;
   }
}

int potriviri(){
	long k=-1,x;
   for(x=0;x<nb;++x){
   	while(k>0 && A[k+1]!=B[x])
        k=pi[k];
      if(A[k+1]==B[x]) ++k;
      if(k==na-1)
        if(++n<1000) v[n]=x-na+1, k=pi[k];
        else return 0;
   }
   return 0;
}


int main(){
	freopen("strmatch.in","r",stdin);
   freopen("strmatch.out","w",stdout);
   gets(A); na=strlen(A);
   gets(B); nb=strlen(B);

   fa_prefix();
   potriviri();

   printf("%ld\n",n);
   for(i=1;i<=n;++i) printf("%ld ",v[i]);
   fclose(stdin); fclose(stdout);
   return 0;
}