Cod sursa(job #328235)

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

char A[Nmax],B[Nmax];
long n,i,na,nb,N;
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;
   }
}

void 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){
      	++n;
        if(n<=1000)v[n]=x-na+1;
        k=pi[k];
      }
   }
}


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();

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