Module memchr::arch::all::rabinkarp

An implementation of the Rabin-Karp substring search algorithm.

Rabin-Karp works by creating a hash of the needle provided and then computing a rolling hash for each needle sized window in the haystack. When the rolling hash matches the hash of the needle, a byte-wise comparison is done to check if a match exists. The worst case time complexity of Rabin-Karp is O(m * n) where m ~ len(needle) and n ~ len(haystack). Its worst case space complexity is constant.

The main utility of Rabin-Karp is that the searcher can be constructed very quickly with very little memory. This makes it especially useful when searching for small needles in small haystacks, as it might finish its search before a beefier algorithm (like Two-Way) even starts.

Structs

• Finder
  A forward substring searcher using the Rabin-Karp algorithm.
• FinderRev
  A reverse substring searcher using the Rabin-Karp algorithm.
• Hash 🔒
  A Rabin-Karp hash. This might represent the hash of a needle, or the hash of a rolling window in the haystack.

Functions

• is_equal_raw 🔒 ^⚠
  Returns true when x[i] == y[i] for all 0 <= i < n.
• is_fast 🔒
  Whether RK is believed to be very fast for the given needle/haystack.