Fast Average-Case Pattern Matching on Weighted Sequences

DOI10.1142/S0129054118430062zbMath1415.68270arXiv1512.01085WikidataQ128673625 ScholiaQ128673625MaRDI QIDQ5384623

Solon P. Pissis, Chang Liu, Carl Barton

Publication date: 24 June 2019

Published in: International Journal of Foundations of Computer Science (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1512.01085

zbMATH Keywords

online algorithmspattern matchinguncertain sequencesweighted strings

Mathematics Subject Classification ID

Online algorithms; streaming algorithms (68W27) Algorithms on strings (68W32)

Related Items

Property Suffix Array with Applications in Indexing Weighted Sequences, On-line weighted pattern matching, Pattern matching and consensus problems on weighted sequences and profiles, Indexing weighted sequences: neat and efficient

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Linear-time computation of prefix table for weighted strings {\&} applications
• Property matching and weighted matching
• Speeding up two string-matching algorithms
• Fast practical multi-pattern matching
• Crochemore's partitioning on weighted strings and applications
• Streaming \(k\)-mismatch with error correcting and applications
• On-Line Pattern Matching on Uncertain Sequences and Applications
• Polynomial-Time Approximation Algorithms for Weighted LCS Problem
• The Complexity of Pattern Matching for a Random String
• Pattern Matching and Consensus Problems on Weighted Sequences and Profiles
• String Processing and Information Retrieval
• Weighted LCS