Algorithms for jumbled indexing, jumbled border and jumbled square on run-length encoded strings

DOI10.1016/j.tcs.2016.04.030zbMath1356.68298OpenAlexW2351354589MaRDI QIDQ507391

Liat Rozenberg, Noa Lewenstein, Gad M. Landau, Amihood Amir, Tirza Hirst, Alberto Apostolico

Publication date: 6 February 2017

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

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

zbMATH Keywords

pattern matchingstring algorithmsabelian borderabelian squarejumbled indexing

Mathematics Subject Classification ID

Algorithms on strings (68W32)

Related Items (7)

On highly palindromic words: the \(n\)-ary case ⋮ Regular Abelian Periods and Longest Common Abelian Factors on Run-Length Encoded Strings ⋮ 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 a theorem concerning partially overlapping subpalindromes of a binary word ⋮ On highly palindromic words: the ternary case ⋮ Bubble-flip -- a new generation algorithm for prefix normal words

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Indexing permutations for binary strings
• Sub-quadratic time and linear space data structures for permutation matching in binary strings
• Algorithms for jumbled indexing, jumbled border and jumbled square on run-length encoded strings
• On approximate jumbled pattern matching in strings
• A note on efficient computation of all abelian periods in a string
• New algorithms for binary jumbled pattern matching
• Binary jumbled string matching for highly run-length compressible texts
• Abelian borders in binary words
• Binary Jumbled Pattern Matching on Trees and Tree-Like Structures
• Efficient Indexes for Jumbled Pattern Matching with Constant-Sized Alphabet
• Prefix Table Construction and Conversion
• ALGORITHMS FOR JUMBLED PATTERN MATCHING IN STRINGS
• Clustered Integer 3SUM via Additive Combinatorics
• On the relationship between histogram indexing and block-mass indexing
• Fast Algorithms for Abelian Periods in Words and Greatest Common Divisor Queries
• Filtering Search: A New Approach to Query-Answering
• Fast Pattern Matching in Strings
• IDENTIFYING ALL ABELIAN PERIODS OF A STRING IN QUADRATIC TIME AND RELEVANT PROBLEMS
• On Hardness of Jumbled Indexing
• Algorithms on Strings

This page was built for publication: Algorithms for jumbled indexing, jumbled border and jumbled square on run-length encoded strings