Near-optimal algorithm to count occurrences of subsequences of a given length

DOI10.1142/S1793830917500422MaRDI QIDQ5367537zbMATH OpenDBLPWikidataFDO

Authors Jose Torres-Jimenez, Idelfonso Izquierdo-Marquez, Daniel Ramirez-Acuna, René Peralta

Publication date 20 October 2017

Published in Discrete Mathematics, Algorithms and Applications (Search for Journal in Brave)

zbMATH Keywords

perfect treecounting subsequences

Mathematics Subject Classification ID

Combinatorics in computer science (68R05) Analysis of algorithms (68W40) Algorithms on strings (68W32)

Recommendations

• Algorithms for subsequence combinatorics
• scientific article; zbMATH DE number 2185636
• Window-accumulated subsequence matching problem is linear
• Compact recognizers of episode sequences
• Longest common subsequence in sublinear space

Cites work

• A fast algorithm for computing a longest common increasing subsequence
• Algorithms for subsequence combinatorics
• Fast computation of a longest increasing subsequence and application
• Faster Algorithms for Computing Longest Common Increasing Subsequences
• Subsequence Combinatorics and Applications to Microarray Production, DNA Sequencing and Chaining Algorithms
• The String-to-String Correction Problem

Cited in

(7)

• Near Linear Time Construction of an Approximate Index for All Maximum Consecutive Sub-sums of a Sequence
• Algorithms for subsequence combinatorics
• Efficient counting of square substrings in a tree
• Detecting k-(Sub-)Cadences and Equidistant Subsequence Occurrences
• AWLCO: All-Window Length Co-Occurrence
• The submatrices character count problem: An efficient solution using separable values
• On the Number of Subsequences When Deleting Symbols From a String

This page was built for publication: Near-optimal algorithm to count occurrences of subsequences of a given length

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