Cod sursa(job #292321)

Utilizator zbarniZajzon Barna zbarni Data 31 martie 2009 00:15:33
Problema Potrivirea sirurilor Scor 14
Compilator cpp Status done
Runda Arhiva educationala Marime 1.09 kb
#include<fstream.h>
#include<string.h>
#define mod1 100003
#define mod2 100019
#define BASE 61
char a[mod1+1],b[mod2+1];
int hash1,hash2,p1,p2;
char pos[mod2+1];
int main()
 {
  ifstream be ("strmatch.in");
  ofstream ki ("strmatch.out");
  be>>a>>b;
  int 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;
   }

  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;
    hashh2=(hashh2-b[i-n]*p2)%mod2;
    hashh1=(hashh1+b[i]*BASE)%mod1;
    hashh2=(hashh2+b[i]*BASE)%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<<'\n',++nr;
  ki.close();
 return 0;
}