Solved

# Rabin-Karp string searching algorithm help

Posted on 2003-11-22

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!