Applications of Succinct Dynamic Compact Tries to Some 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. In this paper, we report our recent work on succinct dynamic compact tries that stores a set of strings of total length n in O(n log ) space supporting pattern matching and in- sert/delete operations in O((jPj= )f (n)) time, where P is a pattern string, = (log n), and f (n) = O((log logn) 2 =log log logn), and its applica- tions to the following string processing problems: (i) online r-suffix tree construction with O(=f (n)) speed up, (ii) succinct substring index with almost same query time and O(=f (n)) speed up on preprocessing time, and (iii) dynamic dictionary matching with O(=f (n)) speed up.