• C

# Rabin-Karp string searching algorithm help

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!
###### Who is Participating?
I wear a lot of hats...

"The solutions and answers provided on Experts Exchange have been extremely helpful to me over the last few years. I wear a lot of hats - Developer, Database Administrator, Help Desk, etc., so I know a lot of things but not a lot about one thing. Experts Exchange gives me answers from people who do know a lot about one thing, in a easy to use platform." -Todd S.

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

Commented:

Experts Exchange Solution brought to you by

Facing a tech roadblock? Get the help and guidance you need from experienced professionals who care. Ask your question anytime, anywhere, with no hassle.

Commented:
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.

Commented:
/* 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);
Commented:
I believe I answered the question of how to calculate d^(m-1) mod q
###### It's more than this solution.Get answers and train to solve all your tech problems - anytime, anywhere.Try it for free Edge Out The Competitionfor your dream job with proven skills and certifications.Get started today Stand Outas the employee with proven skills.Start learning today for free Move Your Career Forwardwith certification training in the latest technologies.Start your trial today
C

From novice to tech pro — start learning today.