Still celebrating National IT Professionals Day with 3 months of free Premium Membership. Use Code ITDAY17

x
Solved

# Rabin-Karp string searching algorithm help

Posted on 2003-11-22
Medium Priority
1,222 Views
Hello everyone,

I was looking at the string searching procedure called RAbin-Karp.  I have a slight problem.  Most implementations have this line in their pseudo code h=d^(m-1) mod q, d being the size of the alphabet (in my case, AT LEAST for case sensitivity of 52 chars) and i need for it to accomodate at least strings of 8 chars (m).  For those familiar with the algorithm, the q is the large prime number chosen to minimize spurios hits.

My question is how does one properly calculates  "h=d^(m-1) mod q" without casing an overflow and without using some large number library (such as GMP).  Most implementations assume an alphabet of 10 chars just for sake of explanation.  But to make it useful, i need to use at least 52 chars.  Am i missing something essential?

Thank you for any input!
0
Question by:enigmaedge
[X]
###### Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

• Help others & share knowledge
• Earn cash & points

LVL 22

Expert Comment

ID: 9805960
52 chars is going to require 6 bits, 8 chars would make a very convenient 48 bits.   Many languages have 64-bit arithmetic.

0

LVL 4

Accepted Solution

dhyanesh earned 500 total points
ID: 9808107
0

LVL 16

Expert Comment

ID: 9895983
enigmaedge,

I'm not familliar with the algorithm but your question suggests m is relatively small, perhaps you could start with 'x = d' and loop 'm-1' times taking 'x = (x * d) mod q' each time. The overhead of adding generic huge maths handling may be far more than the cost of a simple loop.

Hmmm, something tells me this is too obvious to be right.

0

LVL 84

Expert Comment

ID: 10019753
/* Assuming q*q < LONG_MAX */
long powmod(d,m,q){
int p=1;
if( m >= 2 ){
p = powmod(d,m/2,q);
p *= p;
p %= q;
}
if( m%2 ){
p *= d;
p %= q;
}
return p;
}
/* h=d^(m-1) mod q */
h = powmod(d%q,m-1,q);
0

LVL 84

Expert Comment

ID: 10390776
I believe I answered the question of how to calculate d^(m-1) mod q
0

## Featured Post

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Preface I don't like visual development tools that are supposed to write a program for me. Even if it is Xcode and I can use Interface Builder. Yes, it is a perfect tool and has helped me a lot, mainly, in the beginning, when my programs were small…
Windows programmers of the C/C++ variety, how many of you realise that since Window 9x Microsoft has been lying to you about what constitutes Unicode (http://en.wikipedia.org/wiki/Unicode)? They will have you believe that Unicode requires you to use…
The goal of this video is to provide viewers with basic examples to understand recursion in the C programming language.
The goal of this video is to provide viewers with basic examples to understand how to use strings and some functions related to them in the C programming language.
###### Suggested Courses
Course of the Month6 days, 7 hours left to enroll