The Rabin-Karp string matching algorithm is a string matching algorithm that employs a rolling hash function to speed up the search.
Wiki
In computer science, the Rabin–Karp algorithm is a string searching algorithm. For a text of length n and p patterns of combined length m, its average and best case running time is O(n+m) in space O(p), but its worst-case time is O(nm).
Algorithm pseudocode
function RabinKarp(string s[1..n], string sub[1..m])
hsub := hash(sub[1..m]); hs := hash(s[1..m])
for i from 1 to n-m+1
if hs = hsub
if s[i..i+m-1] = sub
return i
hs := hash(s[i+1..i+m])
return not found
Tag usage
The tag rabin-karp can be used for programming related problems in implementing Rabin-Karp algorithm in any programming language. Please avoid theoretical and conceptual questions on StackOverflow using the tag rabin-karp.
