2026-09-20T19:09:56Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:25551 2026-09-05T19:20:14Z ddc:004 open_access

Relative Compressed Reverse Suffix Array Kulekci, Muhammed Oguzhan Parthasarathi, Mano Prakash Shah, Rahul Thankachan, Sharma V. String Matching Text Indexing Data Structures Suffix Trees Suffix trees and suffix arrays are two fundamental data structures in the field of string algorithms. For a string (a.k.a. text or sequence) of length n over an alphabet of size σ, these structures typically require O(nlog n) bits of space. The FM-index provides a compressed representation of the suffix array in ≈ nlog σ bits, allowing for efficient queries on both the suffix array and its inverse array in near logarithmic time. In certain applications, such as approximate pattern matching (i.e., with wildcards, mismatches, edits), there is a need to access the suffix array of a text, as well as the suffix array of text’s reverse. Motivated by this, we explore the possibility of encoding the suffix array of the reversed text in a compact form, assuming the availability of the FM-index for the original text. Our first solution is an O(n)-bit (relative) encoding of the suffix array of the reversed text, with the time for decoding an entry being only O(log^*n) times that of decoding an entry in the text’s suffix array using FM-index. We then demonstrate how to reduce the space to O(n/κ) bits for a parameter κ, while multiplicative factor in time becomes approximately O(κlog^*n+κ³). We can also support inverse suffix array and longest common extension queries on the reversed text. These results are achieved through some careful and non-trivial application of various succinct data structure techniques. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Muhammed Oguzhan Kulekci and Mano Prakash Parthasarathi and Rahul Shah and Sharma V. Thankachan 2026 Is Part Of LIPIcs, Volume 364, 43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.STACS.2026.62 urn:nbn:de:0030-drops-255512 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2026.62 eng https://creativecommons.org/licenses/by/4.0/legalcode