Cod sursa(job #629729)

Utilizator blue_phoenixPosea Elena blue_phoenix Data 3 noiembrie 2011 21:05:35
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.37 kb
#include <stdio.h>
#include <string.h>
#define NMAX 2000004
#define MOD1 666013
#define MOD2 100007
#define B 73

char nna[NMAX],nnb[NMAX];
int na,nb;
int rez[1005],indice=0;
int main(){  
   int i;
   FILE *fin=fopen("strmatch.in","r");
   FILE *fout=fopen("strmatch.out","w");
   fscanf(fin,"%s%s",nnb,nna);
   na=strlen(nna);
   nb=strlen(nnb);
   int nr1=0,nr2=0,hashb1=0,hashb2=0;
   int putere1=1,putere2=1;

   //calculez hash pattern
   for(i=0;i<nb;i++){
      hashb1=(hashb1*B+nnb[i])%MOD1;
      hashb2=(hashb2*B+nnb[i])%MOD2;
      nr1=(nr1*B+nna[i])%MOD1;
      nr2=(nr2*B+nna[i])%MOD2;
      if(i){
        putere1=(putere1*B)%MOD1;
        putere2=(putere2*B)%MOD2;	
      }

   }

   if((nr1==hashb1)&&(nr2==hashb2) ){
      rez[indice++]=0;
      //printf("0\n");
   }
   int c;
   c=na-nb;
   for(i=0;i<c;i++){
      nr1=(nr1-(putere1*nna[i])%MOD1+MOD1);
      nr1=(nr1*B+nna[i+nb])%MOD1; 
 
      nr2=(nr2-(putere2*nna[i])%MOD2+MOD2);
      nr2=(nr2*B+nna[i+nb])%MOD2; 

    //printf("%lld ",nr);
      if((nr1==hashb1)&&(nr2==hashb2)){
        if(indice<1000)rez[indice]=i+1;
        indice++;
       //printf("%d\n",i);
      }
   }

    fprintf(fout,"%d\n",indice);
    if(indice<=1000)
       for(i=0;i<indice;i++)
          fprintf(fout,"%d ",rez[i]);   
      else
         for(i=0;i<1000;i++)
            fprintf(fout,"%d ",rez[i]);   
  
  //printf("%s %s\n",a,b);
return 0;
}