Faster Dynamic Compact Tries with Applications to Sparse Suffix Tree Construction and Other String Problems
Takuya Takagi, Takashi Uemura, Shunsuke Inenaga, Kunihiko Sadakane, Hiroki Arimura · 2013
The dynamic compact trie is a fundamental data structure for a wide range of string processing problems. Jansson, Sadakane, and Sung (LNCS 4855, pp.424-435, FSTTCS 2007) presented the dynamic uncompacted trie data structure of n nodes in O(n log ) space support- ing pattern matching in O((jPj= )f (n)) time and insert/delete opera- tions in O(f (n)) time, where f (n) = ((log logn) 2 =log log logn) is the present best time bound for dynamic predecessor dictionary. Besides its advantage, it is not applicable to linear time suffix tree construction be- cause it has quadratic space complexity there. By extending their work, we present the dynamic compact trie data structure that can store a set of k strings of a single reference string of length n in O(n log +k logn) bits of space even if the total length of edge labels is quadratic in n, still sup- porting pattern matching and insert/delete operations in the same time complexity as Jansson et al.'s dynamic trie. As application, we show that our data structure can be used to solve online construction of the sparse suffix tree (SST) in O((n= )(f (n) + log )) time and O(n log ) bits for evenly taken space r = (log n) with more general bounds.