Cod sursa(job #1076286)

Utilizator buzu.tudor67Tudor Buzu buzu.tudor67 Data 10 ianuarie 2014 00:10:11
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.73 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;
    fi>>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(nr<1000 && hashA1==hashB1 && hashA2==hashB2) sol[++nr]=i-na+1;
         }
         
         fo<<nr<<"\n";
         for(i=1;i<=nr;i++) fo<<sol[i]<<" ";
        }

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