Cod sursa(job #1076289)

Utilizator buzu.tudor67Tudor Buzu buzu.tudor67 Data 10 ianuarie 2014 00:17:58
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.9 kb
#include<fstream>
#include<cstring>
#define maxn 2000005
#define ro1 100007
#define ro2 100021
#define p 97
using namespace std;
ifstream fi("strmatch.in");
ofstream fo("strmatch.out");

char A[maxn],B[maxn];
int hashA1,hashA2;
int hashB1,hashB2;
int na,nb,i,nr=0;
int sol[1005];
int p1,p2;

int main(){
    fi>>A>>B;
    
    na=strlen(A);
    nb=strlen(B);
    
    if(na>nb) fo<<"0";
    else{
         //hashing pentru sirul A
         hashA1=hashA2=0;
         p1=p2=1;
         
         hashA1=(A[0]+0)%ro1;
         hashA2=(A[0]+0)%ro2;
                           
         for(i=1;i<na;i++){
                           hashA1=(hashA1*p+A[i])%ro1;
                           hashA2=(hashA2*p+A[i])%ro2;
                           p1=(p1*p)%ro1;
                           p2=(p2*p)%ro2;
                          }
                          
         //hashing pentru sirul B (primele na caractere)
         hashB1=hashB2=0;
         
         for(i=0;i<na;i++){
                           hashB1=(hashB1*p+B[i])%ro1;
                           hashB2=(hashB2*p+B[i])%ro2;
                          }
                      
         if(hashA1==hashB1 && hashA2==hashB2) sol[++nr]=0;
         
         //hashing pentru sirul B (urmatoarele caractere)                     
         for(i=na;i<nb;i++)
         {
          hashB1=( (hashB1 - (B[i-na]*p1)%ro1 + ro1)*p + B[i] )%ro1;
          hashB2=( (hashB2 - (B[i-na]*p2)%ro2 + ro2)*p + B[i] )%ro2;
          
          if(hashA1==hashB1 && hashA2==hashB2){
                                               nr++;  
                                               if(nr<=1000)sol[nr]=i-na+1;
                                              }
         }
         
         fo<<nr<<"\n";
         if(nr>1000) nr=1000;
         for(i=1;i<=nr;i++) fo<<sol[i]<<" ";
        }

    fi.close();
    fo.close();
    return 0;
}