Which string-matching algorithm uses hashing to find any one of a set of pattern strings in a text?
Show answer
Rabin-Karp algorithm
Rabin-Karp uses a rolling hash to efficiently filter positions in the text. While it has a worst-case of O(nm), its average-case performance is excellent for many practical string-searching tasks.
Also asked as:
- Which algorithm employs hashing to locate pattern strings within a larger body of text?