2023/03/10 by Thierry Lecroq, Lecroq, Thierry
Biochemistry, Genetics and Molecular Biology · Computer Science · #Algorithms and Data Compression #DNA and Biological Computing #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Network Packet Processing and Optimization
paper · pdf · doi:10.48550/arxiv.2303.05799
openalex publication_date 2023/03/10 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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.