Cod sursa(job #292618)

Utilizator zbarniZajzon Barna zbarni Data 31 martie 2009 12:22:28
Problema Potrivirea sirurilor Scor 78
Compilator cpp Status done
Runda Arhiva educationala Marime 1.28 kb
#include<fstream.h>
#include<string.h>
#define mod1 100007
#define mod2 100019
#define BASE 73
#define nx 2000005
char a[nx],b[nx];
long hash1,hash2,p1,p2;
char pos[nx];
int main()
 {
  ifstream be ("strmatch.in");
  ofstream ki ("strmatch.out");
  be>>a>>b;
  long i,n,m,hash1,hashh1,hash2,hashh2,p1,p2,nr=0;
  be.close();
  n=strlen(a);
  m=strlen(b);
  hash1=hash2=hashh1=hashh2=0;
  p1=p2=1;
  for (i=0;i<n;++i)
   {
    hash1=(hash1*BASE+a[i])%mod1;
    hash2=(hash2*BASE+a[i])%mod2;

    if (i)
     p1=(p1*BASE)%mod1,p2=(p2*BASE)%mod2;
   }
  if (n>m){
   ki<<0<<'\n';
   return 0;}

  for (i=0;i<n;++i)
   {
    hashh1=(hashh1*BASE+b[i])%mod1;
    hashh2=(hashh2*BASE+b[i])%mod2;
   }

  if (hash1==hashh1 && hash2==hashh2)
    pos[0]=1,nr++;

  for (i=n;i<m;++i)
   {
    hashh1=((hashh1-(b[i-n]*p1)%mod1+mod1)*BASE+b[i])%mod1;
/*    hashh1=hashh1-(b[i-n]*p1)%mod1;
    hashh2=hashh2-(b[i-n]*p2)%mod2;*/
    hashh2=((hashh2-(b[i-n]*p2)%mod2+mod2)*BASE+b[i])%mod2;
/*    hashh1=(hashh1*BASE+b[i])%mod1;
    hashh2=(hashh2*BASE+b[i])%mod2;*/
    if (hash1==hashh1 && hash2==hashh2)
      pos[i-n+1]=1,nr++;
   }
  ki<<nr<<'\n';
  nr=0;
  for (i=1;i<m && nr<1000;++i)
   if (pos[i])
     ki<<i<<' ',++nr;
  ki<<'\n';
  ki.close();
 return 0;
}