Cod sursa(job #327252)

Utilizator bazubBazu Bogdan bazub Data 27 iunie 2009 19:15:53
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.15 kb
#include<fstream.h>
long i,hash1,hash2,hash1A,hash2A,n,m,P1,P2,PR1=666013,PR2=999017,cate;
char a[2000001],b[2000001];
int sir[2000001];
int main(){
   ifstream fin("strmatch.in");
   ofstream fout("strmatch.out");
   fin.getline(a,20000000);
   fin.getline(b,20000000);
   n=strlen(a);
   m=strlen(b);
   P1=P2=1;
   for(i=0;i<n;i++){
      hash1A=(hash1A*73+a[i])%PR1;
      hash2A=(hash2A*73+a[i])%PR2;
      if(i>0){
         P1=(P1*73)%PR1;
         P2=(P2*73)%PR2;
      }
   }
   for(i=0;i<n;i++){
      hash1=(hash1*73+b[i])%PR1;
      hash2=(hash2*73+b[i])%PR2;
   }
   if(n>m){
      fout<<"0"<<'\n';
      return 0;
   }
   if(hash1==hash1A && hash2==hash2A){
      sir[0]=1;
      cate=1;
   }
   for(i=n;i<m;i++){
      hash1=(((hash1-b[i-n]*P1)%PR1+PR1)*73+b[i])%PR1;
      hash2=(((hash2-b[i-n]*P2)%PR2+PR2)*73+b[i])%PR2;
      if(hash1==hash1A && hash2==hash2A){
         sir[i-n+1]=1;
         cate++;
      }
   }
   fout<<cate<<'\n';
   cate=0;
   for(i=0;i<m && cate<1000;i++)
      if(sir[i]==1){
         fout<<i<<' ';
         cate++;
      }
   fout<<'\n';
   fin.close();
   fout.close();
   return 0;
}