Binary jumbled string matching for highly run-length compressible texts

DOI10.1016/j.ipl.2013.05.007zbMath1284.68691arXiv1206.2523MaRDI 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 structures; jumbled pattern matching; Parikh vectors; string algorithm; prefix normal form; run-lenght encoding

Mathematics Subject Classification ID

68R15: Combinatorics on words

68W32: Algorithms on strings

Related Items

Fast algorithms for abelian periods in words and greatest common divisor queries, 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, Binary jumbled pattern matching on trees and tree-like structures, 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