Implementation of the Rabin Karp Algorithm

Code For Fun

Moving a level above the naive approach to string matching can be done by making use of the comparisons being done during each iteration and using it for the next iteration . In the brute force approach , say we compare T[a…b] with the Pattern P in an iteration and in the next iteration we compare T[a+1….b+1] . So, we are comparing the same characters again and again , which leads to in-efficiency .

The Rabin Karp Algorithm makes a better attempt in solving the above problem . Before giving the implementation we can define a few steps to easily comprehend the Algorithm implementation .

1 . Let us first define the string as a collection of numbers only , say Set Q = {0…9} from which the pattern and text are generated . Then , we will take forward the idea to characters. So, now there are 10 characters…

View original post 467 more words

Advertisements
Standard

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s