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

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

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

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)

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 (4)

• Efficient counting of square substrings in a tree
• The submatrices character count problem: An efficient solution using separable values
• 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

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)