Sub-quadratic time and linear space data structures for permutation matching in binary strings

DOI10.1016/j.jda.2011.08.003zbMath1242.68084OpenAlexW2004360395MaRDI QIDQ414411

M. Sohel Rahman, Tanaeem M. Moosa

Publication date: 11 May 2012

Published in: Journal of Discrete Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jda.2011.08.003

zbMATH Keywords

algorithmsdata structurespattern matchingpermutation matching

Mathematics Subject Classification ID

Combinatorics on words (68R15) Permutations, words, matrices (05A05) Data structures (68P05)

Related Items (16)

Permuted scaled matching ⋮ Fast algorithms for abelian periods in words and greatest common divisor queries ⋮ Binary jumbled pattern matching on trees and tree-like structures ⋮ On the relationship between histogram indexing and block-mass indexing ⋮ Approximating the maximum consecutive subsums of a sequence ⋮ New algorithms for binary jumbled pattern matching ⋮ Binary jumbled string matching for highly run-length compressible texts ⋮ Algorithms for computing abelian periods of words ⋮ Algorithms for jumbled indexing, jumbled border and jumbled square on run-length encoded strings ⋮ Efficient indexes for jumbled pattern matching with constant-sized alphabet ⋮ On approximate jumbled pattern matching in 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 ⋮ Algorithms for Longest Common Abelian Factors ⋮ Bubble-flip -- a new generation algorithm for prefix normal words

Cites Work

• Finding pattern matchings for permutations
• Pattern matching for permutations
• Indexing permutations for binary strings
• On approximate jumbled pattern matching in strings
• ALGORITHMS FOR JUMBLED PATTERN MATCHING IN STRINGS

This page was built for publication: Sub-quadratic time and linear space data structures for permutation matching in binary strings