2026-07-21T20:32:05Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:7340 2024-03-06T10:40:06Z ddc:004 open_access

Representing the Suffix Tree with the CDAWG Belazzougui, Djamal Cunial, Fabio CDAWG suffix tree heavy path decomposition maximal repeat context-free grammar Given a string T, it is known that its suffix tree can be represented using the compact directed acyclic word graph (CDAWG) with e_T arcs, taking overall O(e_T+e_REV(T)) words of space, where REV(T) is the reverse of T, and supporting some key operations in time between O(1) and O(log(log(n))) in the worst case. This representation is especially appealing for highly repetitive strings, like collections of similar genomes or of version-controlled documents, in which e_T grows sublinearly in the length of T in practice. In this paper we augment such representation, supporting a number of additional queries in worst-case time between O(1) and O(log(n)) in the RAM model, without increasing space complexity asymptotically. Our technique, based on a heavy path decomposition of the suffix tree, enables also a representation of the suffix array, of the inverse suffix array, and of T itself, that takes O(e_T) words of space, and that supports random access in O(log(n)) time. Furthermore, we establish a connection between the reversed CDAWG of T and a context-free grammar that produces T and only T, which might have independent interest. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Djamal Belazzougui and Fabio Cunial 2017 Is Part Of LIPIcs, Volume 78, 28th Annual Symposium on Combinatorial Pattern Matching (CPM 2017) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.CPM.2017.7 urn:nbn:de:0030-drops-73402 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2017.7 eng https://creativecommons.org/licenses/by/3.0/legalcode