Cod sursa(job #317247)

Utilizator perticas_catalinperticas catalin perticas_catalin Data 22 mai 2009 22:31:55
Problema Potrivirea sirurilor Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 1.46 kb
#include<string.h>
#include<stdio.h>
FILE*fin=fopen("strmatch.in","r");
FILE*fout=fopen("strmatch.out","w");

#define b 91
#define nm 2000005
#define mod1 666013
#define mod2 999017
 
char s[nm],t[nm];
int dim=0,ptr[nm];
int main()
{
    int hash1=0,hash2=0,h1=0,h2=0,ds,dt,p1=1,p2=1,i;
    fscanf(fin,"%s",&s);
    fscanf(fin,"%s",&t);
    
    ds=strlen(s);
    dt=strlen(t);
    
    for(i=0;i<ds;i++)
    {
      hash1=(hash1*b+s[i]);
      while(hash1>=mod1) hash1-=mod1;
      hash2=(hash2*b+s[i]);
      while(hash2>=mod2) hash2-=mod2;
    }
    
    for(i=0;i<ds;i++)
    {
      h1=(h1*b+t[i]);
      while(h1>=mod1) h1-=mod1;
      h2=(h2*b+t[i]);
      while(h2>=mod2) h2-=mod2;
    }
    
    if(hash1==h1&&hash2==h2) 
    {
      dim++;
      ptr[dim]=0;
    }
    
    for(i=1;i<ds;i++)
    {
       p1=(p1*b)%mod1;
       p2=(p2*b)%mod2;
    }   
    
    for(i=ds;i<dt;i++)
    {
      h1=(h1-t[i-ds]*p1)%mod1;
      if(h1<0) h1+=mod1;
      
      h2=(h2-=t[i-ds]*p2)%mod2;
      if(h2<0) h2+=mod2;
      
      h1=(h1*b+t[i]);
      while(h1>=mod1) h1-=mod1;
      h2=(h2*b+t[i]);
      while(h2>=mod1) h2-=mod2;
      
      if(hash1==h1&&hash2==h2)
      {
        dim++;
        ptr[dim]=i-ds+1;
      }
      
    }
    
    fprintf(fout,"%d\n",dim);
    
    if(dim>1000) dim=1000;
    
    for(i=1;i<=dim;i++)
      fprintf(fout,"%d ",ptr[i]);
    fclose(fin);
    fclose(fout);
    return 0;
}