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)

Full work available at URL https://doi.org/10.1142/S1793830917500422

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)

• Efficient counting of square substrings in a tree
• The submatrices character count problem: An efficient solution using separable values
• Algorithms for subsequence combinatorics
• AWLCO: All-Window Length Co-Occurrence
• Detecting k-(Sub-)Cadences and Equidistant Subsequence Occurrences
• Near Linear Time Construction of an Approximate Index for All Maximum Consecutive Sub-sums of a Sequence
• 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)