Searching long patterns with BNDM
Loading...
Access rights
openAccess
URL
Journal Title
Journal ISSN
Volume Title
A1 Alkuperäisartikkeli tieteellisessä aikakauslehdessä
This publication is imported from Aalto University research portal.
View publication in the Research portal (opens in new window)
View/Open full text file from the Research portal (opens in new window)
Other link related to publication (opens in new window)
View publication in the Research portal (opens in new window)
View/Open full text file from the Research portal (opens in new window)
Other link related to publication (opens in new window)
Authors
Date
2024-11
Department
Major/Subject
Mcode
Degree programme
Language
en
Pages
10
Series
Software - Practice and Experience, Volume 54, issue 11, pp. 2160-2169
Abstract
We present new algorithms for exact string matching of long patterns. Our algorithms read (Formula presented.) -grams at constant distances and are variations of the simplified BNDM algorithm. We demonstrate the competitiveness of our solutions through practical experiments. Many of our algorithms were faster than previous methods for English and DNA patterns between 400 and 50,000 in length. Our algorithms were still better when the preprocessing time was taken into account or when the patterns were taken from a different text of the same type.Description
Publisher Copyright: © 2024 The Authors. Software: Practice and Experience published by John Wiley & Sons Ltd.
Keywords
exact string matching, experimental comparison of algorithms, fingerprint, q-gram
Other note
Citation
Tarhio, J 2024, ' Searching long patterns with BNDM ', Software - Practice and Experience, vol. 54, no. 11, pp. 2160-2169 . https://doi.org/10.1002/spe.3335