Solved

Rabin-Karp string searching algorithm help

Posted on 2003-11-22
8
1,187 Views
Last Modified: 2007-12-19
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
Comment
Question by:enigmaedge
8 Comments
 
LVL 22

Expert Comment

by:grg99
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

by:
dhyanesh earned 125 total points
ID: 9808107
0
 
LVL 16

Expert Comment

by:PaulCaswell
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

by:ozo
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

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

Featured Post

Zoho SalesIQ

Hassle-free live chat software re-imagined for business growth. 2 users, always free.

Question has a verified solution.

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

Summary: This tutorial covers some basics of pointer, pointer arithmetic and function pointer. What is a pointer: A pointer is a variable which holds an address. This address might be address of another variable/address of devices/address of fu…
This is a short and sweet, but (hopefully) to the point article. There seems to be some fundamental misunderstanding about the function prototype for the "main" function in C and C++, more specifically what type this function should return. I see so…
Video by: Grant
The goal of this video is to provide viewers with basic examples to understand and use nested-loops in the C programming language.
The goal of this video is to provide viewers with basic examples to understand and use conditional statements in the C programming language.

896 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question

Need Help in Real-Time?

Connect with top rated Experts

17 Experts available now in Live!

Get 1:1 Help Now