Indexing permutations for binary strings

DOI10.1016/J.IPL.2010.06.012MaRDI QIDQ407548zbMATH OpenOpenAlexFDO

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

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)

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

Cites work

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

Cited in

(13)

• Binary jumbled string matching for highly run-length compressible texts
• Permuted pattern matching algorithms on multi-track strings
• 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
• Orthogonal range searching for text indexing
• Algorithms for longest common abelian factors
• Binary jumbled pattern matching on trees and tree-like structures
• 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)