Approximating the maximum consecutive subsums of a sequence

DOI10.1016/j.tcs.2013.05.032zbMath1284.68483OpenAlexW2092717367MaRDI QIDQ2437755

Ferdinando Cicalese, Oren Weimann, Eduardo Sany Laber, Raphael Yuster

Publication date: 13 March 2014

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

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

zbMATH Keywords

approximate pattern matchingpermutation pattern matchingParikh vectorsmaximum subsequence sum

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Combinatorics on words (68R15) Algorithms on strings (68W32)

Related Items

Generating a Gray code for prefix normal words in amortized polylogarithmic time per word ⋮ Bubble-flip -- a new generation algorithm for prefix normal words

Cites Work

• Sub-quadratic time and linear space data structures for permutation matching in binary strings
• On approximate jumbled pattern matching in strings
• Scaled and permuted string matching
• Fast algorithms for finding disjoint subsequences with extremal densities
• Algorithmic complexity of protein identification: Combinatorics of weighted strings
• Efficient text fingerprinting via Parikh mapping
• A fast string searching algorithm
• Fast Pattern Matching in Strings
• Necklaces, Convolutions, and X + Y
• Computational Science – ICCS 2005