Fast pattern-matching on indeterminate strings

DOI10.1016/j.jda.2006.10.003zbMath1162.68808MaRDI QIDQ954954

W. F. Smyth, Jan Holub, 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

algorithm; string; word; approximate; pattern-matching; Boyer-Moore; indeterminate; sunday

Mathematics Subject Classification ID

68P10: Searching and sorting

68W05: Nonnumerical algorithms

68T10: Pattern recognition, speech recognition

68W25: Approximation algorithms

Related Items

IDPM: An Improved Degenerate Pattern Matching Algorithm for Biological Sequences, Computing covers using prefix tables, Indeterminate string inference algorithms, Indeterminate strings, prefix arrays \& undirected graphs, Linear-time computation of prefix table for weighted strings {\&} applications, A prefix array for parameterized strings, A new approach to the periodicity lemma on strings with holes, A simple fast hybrid pattern-matching algorithm, Covering problems for partial words and for indeterminate strings, Constructing an indeterminate string from its associated graph, Approximate pattern matching on elastic-degenerate text, An aperiodicity problem for multiwords, Indexing a sequence for mapping reads with a single mismatch, Unnamed Item, Subset Seed Automaton, AN ADAPTIVE HYBRID PATTERN-MATCHING ALGORITHM ON INDETERMINATE STRINGS

Uses Software

• Agrep

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• A fast string searching algorithm
• Generalized String Matching
• Fast Pattern Matching in Strings
• Combinatorial Pattern Matching
• String Processing and Information Retrieval