Cod sursa(job #156190)

Utilizator megabyteBarsan Paul megabyte Data 12 martie 2008 13:29:00
Problema Potrivirea sirurilor Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.97 kb
#include <stdio.h>
#include <string.h>
#define INF "strmatch.in"
#define OUF "strmatch.out"
const int NMAX=2000004;
const int LIM=1000;

char a[NMAX],b[NMAX];
int n,m,pi[NMAX],sol[NMAX];

void prefix()
{
   int i,k;
   k=0;pi[1]=0;
   for(i=2;i<=n;++i)
   {
     while(k>0&&a[k+1]!=a[i]) k=pi[k];
     if(a[k+1]==a[i]) ++k;
     pi[i]=k;
   }
}

int main()
{
   FILE *in,*out;
   in=fopen(INF,"r");
   out=fopen(OUF,"w");
   int i,k,nr=0;
   fscanf(in,"%s%s",a+1,b+1);
//   fgets(a+1,NMAX,in);
//   fgets(b+1,NMAX,in);
//   printf("\n");
//   printf("A: %d %s \nB:%d %s",n,a+1,m,b+1);

   n=strlen(a+1);
   m=strlen(b+1);

   prefix();

   k=0;
   for(i=1;i<=m;++i)
   {
      while(k>0&&a[k+1]!=b[i]) k=pi[k];
      if(a[k+1]==b[i]) ++k;
      if(k==n)
      {
	++nr;
	if(nr<=LIM) sol[nr]=i-n;
      }
   }

   fprintf(out,"%d\n",nr);
   for(i=1;i<=nr&&i<=LIM;++i) fprintf(out,"%d ",sol[i]);
   fclose(in);fclose(out);
   return 0;
}