# 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<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*(k1^0) + s1*(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

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

## 1 Answer

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.