The Prague Stringology Conference 2001
Shunsuke Inenaga, Hiromasa Hoshino, Ayumi Shinohara, Masayuki Takeda and Setsuo Arikawa
Construction of the CDAWG for a Trie
| Abstract: |
| Trie is a tree structure to represent a set of strings. When the strings have many common prefixes, the number of nodes in the trie is much less than the total length of the strings. In this paper, we propose an algorithm for constructing the Compact Directed Acyclic Word Graph for a trie, which runs in linear time and space with respect to the number of nodes in the trie. |
| Download paper: |  |
 |
| PostScript |