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 article: Article in PostScript Article in PDF
 PostScript   PDF