Changing Rabin-Karp without modulo to Rabin-Karp with modulo 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&lt;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&lt;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&lt;=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
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.