Optimal-hash Exact String Matching Algorithms
Lecroq Thierry. Arxiv 2023
String matching is the problem of finding all the occurrences of a pattern in a text. We propose improved versions of the fast family of string matching algorithms based on hashing \(q\)-grams. The improvement consists of considering minimal values \(q\) such that each \(q\)-grams of the pattern has a unique hash value. The new algorithms are fastest than algorithm of the HASH family for short patterns on large size alphabets.
Similar Work