Cod sursa(job #412548)

Utilizator adrianraduleaRadulea Adrian adrianradulea Data 5 martie 2010 20:01:48
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.05 kb
#include<stdio.h>
#include<string.h>
FILE *f,*g;
long n,m,i,j,d,ok,prefix[2000500],v[2000500],nr; char model[2000500],sursa[2000500];
int main()
{ f=fopen("strmatch.in","r"); g=fopen("strmatch.out","w");
  fscanf(f,"%s",&model); fscanf(f,"%s",&sursa); m=strlen(model)-1; n=strlen(sursa)-1;
  if(model[0]==model[1]) prefix[1]=-1; prefix[2]=-1; if(model[0]==model[1]&&model[1]!=model[2]) prefix[2]=1; if(model[0]!=model[1]&&model[1]!=model[2]) prefix[2]=0; prefix[0]=-1;
  for(i=2;i<=m;i++)
   { d=i+1; if(d%2==0) d=d/2; else d=d/2+1; j=0; ok=1; if(model[0]==model[i+1]) prefix[i+1]=-1; 
     while(j<=d&&ok)
	  { if(model[j]==model[i-j])
	     { if(model[j+1]!=model[i+1]) prefix[i+1]=j+1;
	       j++; 
		 }
		else ok=0;
      }
   }
  i=0; prefix[m+1]=-1; nr=0; 
  while(i<=n-m+1)
   { j=i;
     while(sursa[j]==model[j-i]&&j-i<=m) j++;
	 if(j-i==m+1) 
	  { nr++; if(nr<=1000) v[nr]=i; 
		i++; 
	  }
	 else i=j-prefix[j-i];
   }
  fprintf(g,"%ld\n",nr); if(nr>=1000) nr=1000; for(i=1;i<=nr;i++) fprintf(g,"%ld ",v[i]);
  fclose(g);
  return 0;
}