When is Rabin-Karp more effective than KMP or Boyer-Moore?

Technology CommunityCategory: StringsWhen is Rabin-Karp more effective than KMP or Boyer-Moore?
VietMX Staff asked 3 years ago

Space Usage favors Rabin-Karp

One major advantage of Rabin-Karp is that it uses O(1) auxiliary storage space, which is great if the pattern string you’re looking for is very large. For example, if you’re looking for all occurrences of a string of length 107 in a longer string of length 109, not having to allocate a table of 107 machine words for a failure function or shift table is a major win. Both Boyer-Moore and KMP use Ω(n) memory on a pattern string of length n, so Rabin-Karp would be a clear win here.