String search algorithms - Naive vs Rabin Karp vs KMP

Naive algorithm is O(n) in average as the probability of a random match is very low and even low for 2 consecutive character matches : 26^2. For 1 million char text and 1000 char word 1.04 million comparisons in average case. Worst case O(m*n) so if the above example 1 billion comparisons.

Rabin karp - used in plagiarism detection. Uses rolling hash - for e.g. if the text is ABCD, and we want to search a word of size 3 then we first compare the hash of ABC which is a*7^0 + b*7^1 + c*7^2. If it doesn't match the hash of the word then we move forward like this 1. first drop A => prev_hash - a*7^0. 2. Then divide the balance by 7 => (prev_hash - a*7^0)/7. 3. Then add D => (prev_hash - a*7^0)/7 + D*7^2. Worst case O(m*n)

KMP - Knuth Morris Pratt - uses a pre-computed table to decide from where to resume search in case of failure. Worst case O(n).