Binary jumbled string matching for highly run-length compressible texts

DOI10.1016/j.ipl.2013.05.007zbMath1284.68691arXiv1206.2523OpenAlexW2167917769MaRDI QIDQ2444848

Gabriele Fici, Steve Kroon, Zsuzsanna Lipták, Golnaz Badkobeh

Publication date: 11 April 2014

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

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

zbMATH Keywords

data structuresjumbled pattern matchingParikh vectorsstring algorithmprefix normal formrun-lenght encoding

Mathematics Subject Classification ID

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

Related Items (6)

Fast algorithms for abelian periods in words and greatest common divisor queries ⋮ 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 ⋮ On prefix normal words and prefix normal forms ⋮ Orthogonal Range Searching for Text Indexing

Cites Work

• Indexing permutations for binary strings
• Sub-quadratic time and linear space data structures for permutation matching in binary strings
• On approximate jumbled pattern matching in strings
• Near Linear Time Construction of an Approximate Index for All Maximum Consecutive Sub-sums of a Sequence
• ALGORITHMS FOR JUMBLED PATTERN MATCHING IN STRINGS
• On Prefix Normal Words

This page was built for publication: Binary jumbled string matching for highly run-length compressible texts