Fujistu Limited
The directed acyclic word graph (DAWG) of a string yy of length nn is the smallest (partial) DFA which recognizes all suffixes of yy with only O(n)O(n) nodes and edges. In this paper, we show how to construct the DAWG for the input string yy from the suffix tree for yy, in O(n)O(n) time for integer alphabets of polynomial size in nn. In so doing, we first describe a folklore algorithm which, given the suffix tree for yy, constructs the DAWG for the reversed string of yy in O(n)O(n) time. Then, we present our algorithm that builds the DAWG for yy in O(n)O(n) time for integer alphabets, from the suffix tree for yy. We also show that a straightforward modification to our DAWG construction algorithm leads to the first O(n)O(n)-time algorithm for constructing the affix tree of a given string yy over an integer alphabet. Affix trees are a text indexing structure supporting bidirectional pattern searches. We then discuss how our constructions can lead to linear-time algorithms for building other text indexing structures, such as linear-size suffix tries and symmetric CDAWGs in linear time in the case of integer alphabets. As a further application to our O(n)O(n)-time DAWG construction algorithm, we show that the set MAW(y)\mathsf{MAW}(y) of all minimal absent words (MAWs) of yy can be computed in optimal, input- and output-sensitive O(n+MAW(y))O(n + |\mathsf{MAW}(y)|) time and O(n)O(n) working space for integer alphabets.
There are no more papers matching your filters at the moment.