Question

Can anyone explain me the Rabin Karp algorithm? Or any other string matching algorithm, except the naive general matching, ofcourse.

Answer 1

If you get some info from somewhere post it, because i'm also interested in it :)

Answer 2

I could give intuitive reason behind an algorithm called KMP (Knuth-Morris-Pratt). Suppose you were given a string "ABCDEF" to search in a text, every time you find a mismatch you know that no character in "ABCDEF" repeats itself hence you shift it by whole search string. Of course, if some characters repeat like "ABCABD" you shift lesser. You shift least when all characters are same, say "AAAAA". You may look to wiki for details but this is the intuition (in calculating how much to jump).

Answer 3

In practical applications, we generally require to search more than one string from a given text (eg to detect plagiarism). Hence if we have 3 strings, we would be running string search 3 times. Usual string search (like KMP) would not use the knowledge attained while searching for first time, when it is searching second string. Alternative could be to map each string in the text to a (probably unique)number (hashing). String to be searched is also converted to a number and existence of string in text takes O(1) as we just need to check corresponding location in the hash table. Of course, depending on hashing function, we could have two strings with same number in which case it could be little more complicated. This is the essence of Rabin-Karp algorithm.