2026-07-23T22:19:24Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:6071 2024-03-06T10:37:35Z ddc:004 open_access

Fully-online Construction of Suffix Trees for Multiple Texts Takagi, Takuya Inenaga, Shunsuke Arimura, Hiroki suffix trees DAWGs multiple texts online algorithms We consider fully-online construction of indexing data structures for multiple texts. Let T = {T_1, ..., T_K} be a collection of texts. By fully-online, we mean that a new character can be appended to any text in T at any time. This is a natural generalization of semi-online construction of indexing data structures for multiple texts in which, after a new character is appended to the kth text T_k, then its previous texts T_1, ..., T_k-1 will remain static. Our fully-online scenario arises when we maintain dynamic indexes for multi-sensor data. Let N and sigma denote the total length of texts in T and the alphabet size, respectively. We first show that the algorithm by Blumer et al. [Theoretical Computer Science, 40:31-55, 1985] to construct the directed acyclic word graph (DAWG) for T can readily be extended to our fully-online setting, retaining O(N log sigma)-time and O(N)-space complexities. Then, we give a sophisticated fully-online algorithm which constructs the suffix tree for T in O(N log sigma) time and O(N) space. A key idea of this algorithm is synchronized maintenance of the DAWG and the suffix tree. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Takuya Takagi and Shunsuke Inenaga and Hiroki Arimura 2016 Is Part Of LIPIcs, Volume 54, 27th Annual Symposium on Combinatorial Pattern Matching (CPM 2016) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.CPM.2016.22 urn:nbn:de:0030-drops-60719 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2016.22 eng https://creativecommons.org/licenses/by/3.0/legalcode