Abstract
The compact directed acyclic word graph (CDAWG) can be understood in two equivalent ways: as the edge-compacted DAWG of the string, and as the DAG obtained from the suffix tree by merging isomorphic subtrees.
By exploiting these two perspectives in complementary ways, we demonstrate how to construct the CDAWG for a (reversed) input string of length $n$. Specifically, for an input string with $e_L$ edges, we can build it in $O(e_L\log n\log(n/r))$ time while using $O(r\log(n/r)+e_L)$ words of working space. Here, $r$ denotes the number of BWT-runs of the input string.
Moreover, this method relies on the fully functional compressed suffix tree by Gagie, Navarro, and Prezza, which has size $O(r\log(n/r))$.
Conclusion
This approach shows promising time and space complexity for constructing CDAWGs, providing new insights and tools for string processing.
Blogger's Review: The efficient construction method for CDAWGs proposed in this paper leverages the structural characteristics of suffix trees, showcasing innovation in algorithms for string graph structures. It significantly advances research in the field of string processing.