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

DOI10.1142/S1793830917500422zbMATH Open1398.68709DBLPjournals/dmaa/Torres-JimenezI17WikidataQ47663982 ScholiaQ47663982MaRDI QIDQ5367537FDOQ5367537

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)

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

zbMATH Keywords

perfect treecounting subsequences

Mathematics Subject Classification ID

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

Cites Work

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

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)