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

algorithmstringwordapproximateBoyer-Moorepattern-matchingindeterminatesunday

Mathematics Subject Classification ID

Pattern recognition, speech recognition (68T10) Searching and sorting (68P10) 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

• 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?)
• A fast string searching algorithm
• Alternative algorithms for bit-parallel string matching.
• Combinatorial Pattern Matching
• Fast Pattern Matching in Strings
• Generalized String Matching

Cited in

(28)

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

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)