Cod sursa(job #235780)

Utilizator eugen.nodeaEugen Nodea eugen.nodea Data 25 decembrie 2008 20:43:25
Problema Potrivirea sirurilor Scor 36
Compilator cpp Status done
Runda Arhiva educationala Marime 0.78 kb
# include <stdio.h>
# include <string.h>
# define nmax 2000002
char A[nmax],B[nmax];
int Prefix[nmax], p[1024];
long n,m;

void prefix(void)
{
  int k=-1;
  long i;
  Prefix[0]=-1;
  for (i=1;i<n;i++)
    {
	while (k>-1 && A[k+1]!=A[i])
	    k=Prefix[k];
	if (A[k+1]==A[i]) k++;
	Prefix[i]=k;
    }
}

int main(){
  long i,k,j=0;

  freopen("strmatch.in", "r", stdin);
  freopen("strmatch.out", "w", stdout);
  gets(A); n=strlen(A);
  gets(B); m=strlen(B);
  prefix();
  k=-1;
  for (i=0;i<m;i++){
	while (k>-1 && A[k+1]!=B[i]) k=Prefix[k];
	if (A[k+1]==B[i]) k++;
	if (k==n-1){
	     k=Prefix[n-1],j++;
	     if (j<=100) p[j]=i-n+1;
 	 }       
   }
  printf("%ld\n",j);
  if (j>1000) j=1000;
  for (i=1;i<=j;i++)
     printf("%ld ", p[i]);
  return 0;
}