Cod sursa(job #950839)

Utilizator Andrei1998Andrei Constantinescu Andrei1998 Data 18 mai 2013 13:32:36
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.77 kb
#include <fstream>
#include <cstring>

using namespace std;

#define mod1 1234
#define mod2 1235
#define p1 73
#define p2 74

char pe_cine[2000007];
char sir[2000007];
int mach[2000007];

int main()
{
    ifstream cin("strmatch.in");
    ofstream cout("strmatch.out");
    
    cin.get(pe_cine,2000007);
    cin.get();
    cin.get(sir,2000007);
    int n1=strlen(pe_cine),i;
    int n2=strlen(sir);
    
    if(n1>n2)
    {
      cout<<"0\n";
      //cout<<"spec"<<endl;
      //system("PAUSE");
      cin.close();
      cout.close();
      return 0;
    }
    
    int hash_mic1=0,hash_mic2=0;
    int hash_mare1=0,hash_mare2=0;
    int coef1=1,coef2=1;
    
    for(i=0;i<n1;i++)
    {
       hash_mic1=(hash_mic1*p1+pe_cine[i])%mod1;                   
       hash_mare1=(hash_mare1*p1+sir[i])%mod1;
       hash_mic2=(hash_mic2*p2+pe_cine[i])%mod2;                   
       hash_mare2=(hash_mare2*p2+sir[i])%mod2;
       
       if(i!=0)
       {
         coef1=(coef1*p1)%mod1;
         coef2=(coef2*p2)%mod2;      
       }
       //cout<<hash_mic1<<' '<<' '<<hash_mare1<<' '<<' '<<coef1<<' '<<endl;    
    }
    int nr=0;
    
    for(i=n1;i<n2;i++)
    {
       if(hash_mic1==hash_mare1 && hash_mic2==hash_mare2)
          mach[nr++]=i-n1;     
       hash_mare1=(((((hash_mare1-(sir[i-n1]*coef1)%mod1+mod1)%mod1)*p1)%mod1+sir[i])%mod1);
       hash_mare2=(((((hash_mare2-(sir[i-n1]*coef2)%mod2+mod2)%mod2)*p2)%mod2+sir[i])%mod2);   
    }
    
    if(hash_mic1==hash_mare1 && hash_mic2==hash_mare2)
       mach[nr++]=n2-n1;
    
    cout<<nr<<'\n';
    if(nr>1000)
      nr=1000;
    
    for(i=0;i<nr;i++)
      cout<<mach[i]<<' ';
    cout<<'\n';
    
    cin.close();
    cout.close();
   // system("PAUSE");
    return 0;
}