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..its like this now.
(this is for starting pattern length of the big string)
3 unsigned long long int k2 = *(s1+i);
4 p1 += k2 * k1;
5 k1 = (k1 * 31);
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;
3 unsigned long long int k3 = *(str+j);
4 p2 += k3 * k4;
5 k4 = (k4 *31);
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);
3 printf("p1 and p2 are %d nd %d\n",p1,p2);
4 if ( p2 == p1)
6 r1 = 1;
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));
15 if ( r1 == 0)
where str is the big string,s1 is pattern string.
I tested for multiple inputs an i am getting correct answers for all of them but its taking a lot of time..i then realized its 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:
Please help me out with this,i tried searching in net but could not find help.
Thanks in Advance!