2
$\begingroup$

I am trying to solve a string matching problem using Rabin-karp algorithm.

I made use of Horner's method for calculating hash function, but I forgot to use modulo operator. It's like this now.

(this is for starting pattern length of the big string)

  1     for(i=0;i<l1;i++)
  2     {
  3         unsigned long long int k2 = *(s1+i);
  4         p1 += k2 * k1;
  5         k1 = (k1 * 31);
  6     }

where s1 is a string containing characters,and its like

s1[0]*(k1^0) + s1[1]*(k1^1) and so on.

and I did the same for the pattern we need to find:

  0     unsigned long long int j;
  1     for(j=0;j<l1;j++)
  2     {
  3         unsigned long long int k3 = *(str+j);
  4         p2 += k3 * k4;
  5         k4 = (k4 *31);
  6     }

Now I am going through strings of length = pattern length in the big string. Code for that is:

  0  long long int ll1 = strlen(s1),ll2=strlen(str); 
  1     for(j=1;j<=ll2;j++) 
  2     { 
  3         printf("p1 and p2 are %d nd %d\n",p1,p2); 
  4         if ( p2 == p1) 
  5         { 
  6             r1 = 1; 
  7             break; 
  8         } 
  9         long int w1 = *(str+j-1); 
 10         p2 -= w1;      
 11         p2 = p2/31; 
 12         long int lp = *(str+j+l1-1); 
 13         p2 += ((lp *vp)); 
 14  } 
 15     if ( r1 == 0) 
 16     { 
 17         printf("n\n"); 
 18     } 
 19     else
 20      {
 21           printf("y\n");
 22      }
 23    }

where str is the big string, s1 is pattern string.

I tested for multiple inputs and I am getting correct answers for all of them but its taking a lot of time. I then realized it's because of high calculations needed when the pattern string is too long and if we use a modulo operator we can minimize those calculations.

My question is how to incorporate modulo operator in this code while searching for patterns?

My entire code: http://ideone.com/81hOiU

$\endgroup$
  • $\begingroup$ This seems like an implementation question, and so off-topic here. $\endgroup$ – Yuval Filmus Mar 26 '17 at 10:12
1
$\begingroup$

Don't wait to do the modular reduction at the end. Every time you do an addition or multiplication, immediately reduce modulo the modulus. This keeps all intermediate results small.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.