Indexing permutations for binary strings

DOI10.1016/J.IPL.2010.06.012zbMATH Open1234.68479OpenAlexW1968531819MaRDI QIDQ407548FDOQ407548

Authors: Tanaeem M. Moosa, M. Sohel Rahman 

Publication date: 27 March 2012

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

Full work available at URL: https://doi.org/10.1016/j.ipl.2010.06.012

Recommendations

• Sorting permutations and binary strings by length-weighted rearrangements
• The sorting index and permutation codes
• Deterministic indexing for packed strings
• Fast and simple jumbled indexing for binary run-length encoded strings
• Sub-quadratic time and linear space data structures for permutation matching in binary strings
• scientific article; zbMATH DE number 436084
• Computing permutation encodings
• The compressed permuterm index
• Efficient indexing algorithms for one-dimensional discretely-scaled strings
• The insertion encoding of permutations

zbMATH Keywords

pattern matchingcombinatorial problems

Mathematics Subject Classification ID

Combinatorics in computer science (68R05) Data structures (68P05) Algorithms on strings (68W32) Computing methodologies for text processing; mathematical typography (68U15)

Cites Work

• Finding pattern matchings for permutations
• Pattern matching for permutations
• Necklaces, Convolutions, and X + Y

Cited In (12)

• Binary jumbled string matching for highly run-length compressible texts
• New algorithms for binary jumbled pattern matching
• Sub-quadratic time and linear space data structures for permutation matching in binary strings
• On prefix normal words and prefix normal forms
• On approximate jumbled pattern matching in strings
• Fast algorithms for abelian periods in words and greatest common divisor queries
• Algorithms for computing abelian periods of words
• Algorithms for longest common abelian factors
• Binary jumbled pattern matching on trees and tree-like structures
• Orthogonal Range Searching for Text Indexing
• Algorithms for jumbled indexing, jumbled border and jumbled square on run-length encoded strings
• Efficient indexes for jumbled pattern matching with constant-sized alphabet

This page was built for publication: Indexing permutations for binary strings

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q407548)