Linear-time computation of prefix table for weighted strings {\&} applications

DOI10.1016/j.tcs.2016.04.029zbMath1356.68299OpenAlexW2342939298MaRDI QIDQ507393

Solon P. Pissis, Carl Barton, Chang Liu

Publication date: 6 February 2017

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2016.04.029

zbMATH Keywords

algorithms on stringsuncertain sequencesweighted strings

Mathematics Subject Classification ID

Data structures (68P05) Algorithms on strings (68W32)

Related Items

Crochemore's partitioning on weighted strings and applications, Fast Average-Case Pattern Matching on Weighted Sequences, On-line weighted pattern matching, Pattern matching and consensus problems on weighted sequences and profiles, Indexing weighted sequences: neat and efficient, Streaming \(k\)-mismatch with error correcting and applications

Uses Software

• PEAR

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Enhanced string covering
• Fast profile matching algorithms - A survey
• Fast pattern-matching on indeterminate strings
• An on-line string superprimitivity test
• Prefix Table Construction and Conversion
• Fast and Simple Computations Using Prefix Tables Under Hamming and Edit Distance
• Polynomial-Time Approximation Algorithms for Weighted LCS Problem
• Space-Efficient Preprocessing Schemes for Range Minimum Queries on Static Arrays
• Linear-Time Computation of Prefix Table for Weighted Strings
• Linear work suffix array construction
• Approximate All-Pairs Suffix/Prefix Overlaps
• Fast Pattern Matching in Strings
• Probabilistic ancestral sequences and multiple alignments
• Property Matching and Weighted Matching
• Approximate Matching in Weighted Sequences
• Algorithms on Strings
• Weighted LCS