Rabin-Karp Algorithm
String searching algorithm using hashing to find any one of a set of pattern strings in a text.
Pattern Hash-
Current Window Hash-
ABCCDDAEFG
CDD
Status: Enter text and pattern to start
1function rabinKarp(text, pattern):
2 n = text.length, m = pattern.length
3 p = hash(pattern), t = hash(text[0..m])
4
5 for i = 0 to n-m:
6 if p == t:
7 if checkChars(text, pattern, i):
8 print "Pattern found at " + i
9
10 if i < n-m:
11 t = rollHash(t, text[i], text[i+m])
Complexity
Time (Avg)O(N + M)
Time (Worst)O(NM)