New algorithms for binary jumbled pattern matching

DOI10.1016/j.ipl.2013.04.013zbMath1284.68698arXiv1210.6176OpenAlexW2023986152MaRDI QIDQ2444765

Szymon Grabowski, Emanuele Giaquinta

Publication date: 11 April 2014

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1210.6176

zbMATH Keywords

combinatorial problemsrun-length encodingstring algorithmsjumbled pattern matchingword-level parallelismParikh vectors

Mathematics Subject Classification ID

Combinatorics on words (68R15) Algorithms on strings (68W32)

Related Items (8)

Binary jumbled pattern matching on trees and tree-like structures ⋮ Algorithms for computing abelian periods of words ⋮ Algorithms for jumbled indexing, jumbled border and jumbled square on run-length encoded strings ⋮ Generating a Gray code for prefix normal words in amortized polylogarithmic time per word ⋮ On prefix normal words and prefix normal forms ⋮ On infinite prefix normal words ⋮ Unnamed Item ⋮ Bubble-flip -- a new generation algorithm for prefix normal words

Cites Work

• Unnamed Item
• Unnamed Item
• Indexing permutations for binary strings
• Sub-quadratic time and linear space data structures for permutation matching in binary strings
• Scaled and permuted string matching
• Near Linear Time Construction of an Approximate Index for All Maximum Consecutive Sub-sums of a Sequence
• Dynamic ordered sets with exponential search trees

This page was built for publication: New algorithms for binary jumbled pattern matching