Cod sursa(job #2075717)

Utilizator Garen456Paun Tudor Garen456 Data 25 noiembrie 2017 17:04:47
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.14 kb
#include <bits/stdc++.h>
#define P 73
#define MOD1 100007
#define MOD2 100021
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
char a[2000005],b[2000005];
bool V[2000005];
int na,nb;
int main()
{  fin>>a>>b;
  na=strlen(a);
  nb=strlen(b);
  int p1=1,p2=1,hA1=0,hA2=0;

  for(int i=0;i<na;++i)
   {
       hA1=( hA1*P+a[i])%MOD1;
       hA2=(hA2*P+a[i])%MOD2;
       if(i!=0)
        {p1=(p1*P)%MOD1;
        p2=(p2*P)%MOD2;
        }
   }
   if(na>nb)
   {fout<<0; return 0;}

   int hB1=0,hB2=0;
   for(int i=0;i<na;++i)
   { hB1=(hB1*P+b[i])%MOD1;
     hB2=(hB2*P+b[i])%MOD2;
   }
   int Nr=0;
   if(hA1==hB1 && hA2==hB2)
         V[0]=1,Nr++;
 // fout<<hA1<<" "<<hA2<<" "<<hB1<<" "<<hB2<<"\n";
   for(int i=na;i<nb;++i)
   { hB1=((hB1-(b[i-na]*p1)%MOD1 +MOD1 )*P+ b[i])%MOD1;
     hB2=((hB2-(b[i-na]*p2)%MOD2 +MOD2 )*P+ b[i])%MOD2;
   if(hA1==hB1 && hA2==hB2)
         V[i-na+1]=1,++Nr;
     //    fout<<hA1<<" "<<hA2<<" "<<hB1<<" "<<hB2<<"\n";
   }
   fout<<Nr<<"\n";
   Nr=0;

   for(int i=0;i<nb && Nr<1000;++i)
      if(V[i])
      ++Nr,fout<<i<<" ";



    return 0;
}