Cod sursa(job #191277)

Utilizator nicolaetitus12Nicolae Titus nicolaetitus12 Data 25 mai 2008 20:14:41
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.2 kb
#include <string.h>
#include <stdio.h>
#define N 2000010 //lungimea sirului
#define M 2000010 //lungimea subsirului
char sir[N],subsir[M];
long pi[M];
long stiva[1010],vf=0;
void adauga(long p)
{stiva[vf++]=p;}

void prefix()
{long i,k;
 pi[1]=0;
 for (i=2;i<strlen(subsir);i++)
 {for(k=i-1;k>0&&subsir[i]!=subsir[pi[k]+1];k=pi[k])
  {}
  if(k>0)
  {pi[i]=pi[k]+1;
  }
  else if(subsir[1]==subsir[i])
  {pi[i]=1;
  }
 }
}

int main ()
{FILE *f,*fout;
 f=fopen("strmatch.in","r");
 fout=fopen("strmatch.out","w");
 long i,k,nr,n,m;
 fgets(subsir,M,f);
 fgets(sir,N,f);
 for(i=strlen(subsir)+1;i>0;i--)
 {subsir[i]=subsir[i-1];}
 for(nr=0,i=strlen(sir)+1;i>0;i--)
 {sir[i]=sir[i-1];}
 subsir[0]=' ';sir[0]=' ';
 subsir[strlen(subsir)-1]=subsir[strlen(subsir)];
 prefix();
 n=strlen(sir);
 m=strlen(subsir);
 for (i=1;i<=strlen(sir);)
 {if(sir[i]==subsir[1])
  {k=1;
   while(k<=m&&k+i<=n&&sir[i+k]==subsir[k+1])
    k++;
   if(k==m-1)
   {if(nr<1000)adauga(i);
    nr++;
   }
   if(pi[k]>0)
   {i+=k-pi[k];
   }
   else
   {i++;}
  }
  else i++;
 }
 
 fprintf(fout,"%ld\n",nr);
 for (i=0;i<vf;i++)
 {fprintf(fout,"%ld ",stiva[i]-1);
 }
 fclose(fout);
 return 0;
}