Sorting: Rabin Karp

**Big O: **O(n+m) average, O(nm) worst case when using a bad hash function and resorting to brute force

Rabin Karp relies on a hash function.  Essentially, you hash the given pattern and then compare the pattern’s hash to the given text’s hash.  If the hash matches, then you compare the actual text string to the pattern string in case the hashes matched incidentally.  Otherwise you call an updateHash function, which replaces the first text character with the next one in line.

Loop through text
If text. hash == pattern.hash{
if compare(pattern, text){
return index;
}
}
updateHash();

**Example: **An example updateHash function might look something like this:

updateHash(oldHash, base, oldChar, power, newChar, length){
return (oldHash – oldChar(base^power))*base + newChar
}