Linear-time computation of DAWGs, symmetric indexing structures, and MAWs for integer alphabets

DOI10.1016/J.TCS.2023.114093zbMATH Open1520.68229arXiv2307.01428OpenAlexW4385360496MaRDI QIDQ6093582FDOQ6093582

Authors: Yuta Fujishige, Yuki Tsujimaru, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda

Publication date: 7 September 2023

Published in: Theoretical Computer Science (Search for Journal in Brave)

Abstract: The directed acyclic word graph (DAWG) of a string

y

of length

n

is the smallest (partial) DFA which recognizes all suffixes of

y

with only

O (n)

nodes and edges. In this paper, we show how to construct the DAWG for the input string

y

from the suffix tree for

y

, in

O (n)

time for integer alphabets of polynomial size in

n

. In so doing, we first describe a folklore algorithm which, given the suffix tree for

y

, constructs the DAWG for the reversed string of

y

in

O (n)

time. Then, we present our algorithm that builds the DAWG for

y

in

O (n)

time for integer alphabets, from the suffix tree for

y

. We also show that a straightforward modification to our DAWG construction algorithm leads to the first

O (n)

-time algorithm for constructing the affix tree of a given string

y

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