Cod sursa(job #296292)

Utilizator adrianraduleaRadulea Adrian adrianradulea Data 4 aprilie 2009 16:08:59
Problema Potrivirea sirurilor Scor 18
Compilator cpp Status done
Runda Arhiva educationala Marime 0.73 kb
#include<stdio.h>
#include<string.h>
FILE *f,*g;
char a[2000005],b[2000005];
long pi[2000005],c[1005],nr,k,i,j,n,m,max,ok,poz;
int main()
{ f=fopen("strmatch.in","r"); g=fopen("strmatch.out","w");
  fscanf(f,"%s",a); fscanf(f,"%s",b);
  n=strlen(a)-1; m=strlen(b)-1;
  for(i=0;i<=n;i++)
   { j=-1; k=-1; if(a[0]!=a[i+1]) k=0;
     while(j<i)
      if(a[j+1]==a[i-j-1])
       { j++;
	 if(a[j+1]!=a[i+1]) k=j+1;
       }
      else j=i+1;
     pi[i]=i+1-k;
   }
  i=0; nr=0;
  while(i<=m-n)
   { j=0; ok=1;
     while(j<=n&&ok) if(a[j]==b[i+j]) j++; else { poz=j; ok=0; }
     if(ok) { nr++; if(nr<1001) c[nr]=i; }
     i+=pi[poz-1];
   }
  fprintf(g,"%ld\n",nr);
  for(i=1;i<=nr;i++) fprintf(g,"%ld ",c[i]);
  return 0;
}