Fast pattern-matching on indeterminate strings

DOI10.1016/J.JDA.2006.10.003MaRDI QIDQ954954zbMATH OpenOpenAlexFDO

Authors Jan Holub, W. F. Smyth, Shu Wang

Publication date 18 November 2008

Published in Journal of Discrete Algorithms (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.jda.2006.10.003

zbMATH Keywords

algorithmapproximateBoyer-Mooreindeterminatepattern-matchingstringsundayword

Mathematics Subject Classification ID

Searching and sorting (68P10) Pattern recognition, speech recognition (68T10) Nonnumerical algorithms (68W05) Approximation algorithms (68W25)

Recommendations

• An adaptive hybrid pattern-matching algorithm on indeterminate strings
• Fast string matching with mismatches
• Fastest Pattern Matching in Strings
• Indeterminate string inference algorithms
• Fast and flexible string matching by combining bit-parallelism and suffix automata

Cites work

• A fast string searching algorithm
• Alternative algorithms for bit-parallel string matching.
• Combinatorial Pattern Matching
• Fast Pattern Matching in Strings
• Generalized String Matching
• scientific article; zbMATH DE number 3471577 (Why is no real title available?)
• scientific article; zbMATH DE number 2052918 (Why is no real title available?)
• scientific article; zbMATH DE number 1754502 (Why is no real title available?)

Cited in

(32)

• Constructing an indeterminate string from its associated graph
• Order-preserving pattern matching indeterminate strings
• A new approach to regular \& indeterminate strings
• Approximate pattern matching on elastic-degenerate text
• Fast string matching in stationary ergodic sources
• An aperiodicity problem for multiwords
• Indexing a sequence for mapping reads with a single mismatch
• Computing covers using prefix tables
• The finite automata approaches in stringology
• Deterministic Sampling–A New Technique for Fast Pattern Matching
• Subset Seed Automaton
• scientific article; zbMATH DE number 5717259 (Why is no real title available?)
• An adaptive hybrid pattern-matching algorithm on indeterminate strings
• Indeterminate string inference algorithms
• IDPM: an improved degenerate pattern matching algorithm for biological sequences
• Indeterminate strings, prefix arrays \& undirected graphs
• Linear-time computation of prefix table for weighted strings {\&} applications
• Even faster elastic-degenerate string matching via fast matrix multiplication
• A prefix array for parameterized strings
• Order-preserving pattern matching indeterminate strings
• Pattern matching on elastic-degenerate text with errors
• CSA++: Fast Pattern Search for Large Alphabets
• A Memory-Efficient and Modular Approach for Large-Scale String Pattern Matching
• Algorithms – ESA 2005
• Elastic-Degenerate String Matching via Fast Matrix Multiplication
• On the complexity of indeterminate strings matching
• A unifying taxonomy of pattern matching in degenerate strings and founder graphs
• Reconstructing general matching graphs
• Practical KMP/BM style pattern-matching on indeterminate strings
• A new approach to the periodicity lemma on strings with holes
• A simple fast hybrid pattern-matching algorithm
• A faster algorithm for matching a set of patterns with variable length don't cares

Describes a project that uses

Uses Software

• Agrep

This page was built for publication: Fast pattern-matching on indeterminate strings

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