Prefix Sorting DFAs: a Recursive Algorithm
share
In the past thirty years, numerous algorithms for building the suffix array of a string have been proposed. In 2021, the notion of suffix array was extended from strings to DFAs, and it was shown that the resulting data structure can be built in O(m^2 + n^5/2) time, where n is the number of states and m is the number of edges [SODA 2021]. Recently, algorithms running in O(mn) and O(n^2log n) time have been described [CPM 2023]. In this paper, we improve the previous bounds by proposing an O(n^2) recursive algorithm inspired by Farach's algorithm for building a suffix tree [FOCS 1997]. To this end, we provide insight into the rich lexicographic and combinatorial structure of a graph, so contributing to the fascinating journey which might lead to solve the long-standing open problem of building the suffix tree of a graph.
READ FULL TEXT