Improving practical exact string matching

DOI10.1016/J.IPL.2009.11.010MaRDI QIDQ990135zbMATH OpenOpenAlexFDO

Authors Branislav Ďurian, Jan Holub, Hannu Peltola, Jorma Tarhio

Publication date 2 September 2010

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.ipl.2009.11.010

zbMATH Keywords

algorithmsstring matchingbit-parallelismexperimental comparison

Mathematics Subject Classification ID

Searching and sorting (68P10) Parallel algorithms in computer science (68W10)

Recommendations

• Tuning BNDM with \(q\)-grams
• Alternative algorithms for bit-parallel string matching.
• Fast and flexible string matching by combining bit-parallelism and suffix automata
• Efficient variants of the backward-oracle-matching algorithm
• String matching with lookahead

Cites work

• scientific article; zbMATH DE number 801745 (Why is no real title available?)
• A Method to Overcome Computer Word Size Limitation in Bit-Parallel Pattern Matching
• A fast string searching algorithm
• Alternative algorithms for bit-parallel string matching.
• Fast and flexible string matching by combining bit-parallelism and suffix automata
• Fast exact string matching algorithms
• NR-grep: A fast and flexible pattern-matching tool
• Shift-or string matching with super-alphabets
• The wide window string matching algorithm

Cited in

(18)

• Fast algorithms for single and multiple pattern Cartesian tree matching
• String matching with lookahead
• Fast and flexible string matching by combining bit-parallelism and suffix automata
• Average complexity of backward \(q\)-gram string matching algorithms
• Alternative algorithms for bit-parallel string matching.
• Top-k Substring Matching for Auto-Completion
• Improved and self-tuned occurrence heuristics
• Run-Length Encoded Nondeterministic KMP and Suffix Automata
• Tuning BNDM with \(q\)-grams
• scientific article; zbMATH DE number 1094183 (Why is no real title available?)
• A filtration method for order-preserving matching
• Fast Cartesian tree matching
• Improved online algorithms for jumbled matching
• Order-preserving pattern matching indeterminate strings
• Order-preserving pattern matching indeterminate strings
• Efficient variants of the backward-oracle-matching algorithm
• Lyndon factorization algorithms for small alphabets and run-length encoded strings
• Generalized String Matching

This page was built for publication: Improving practical exact string matching

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q990135)