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.
http://www.spoj.com/problems/SUB_PROB/
(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 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:
http://ideone.com/81hOiU
Please help me out with this,i tried searching in net but could not find help.
Thanks in Advance!