Linear-time computation of DAWGs, symmetric indexing structures, and MAWs for integer alphabets
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 …
which recognizes all suffixes of y with only O (n) nodes and edges. In this paper, we show …
Linear-size suffix tries and linear-size CDAWGs simplified and improved
S Inenaga - Acta Informatica, 2024 - Springer
The linear-size suffix tries (LSTries)(Crochemore et al. in Theor Comput Sci 638: 171–178,
2016) are a version of suffix trees in which the edge labels are single characters, yet are …
2016) are a version of suffix trees in which the edge labels are single characters, yet are …