2026-07-23T20:16:11Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:19324 2024-03-06T11:03:46Z ddc:004 open_access

Prefix Sorting DFAs: A Recursive Algorithm Cotumaccio, Nicola Suffix Array Burrows-Wheeler Transform FM-index Recursive Algorithms Graph Theory Pattern Matching 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² + 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²log n) time have been described [CPM 2023]. In this paper, we improve the previous bounds by proposing an O(n²) 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Nicola Cotumaccio 2023 Is Part Of LIPIcs, Volume 283, 34th International Symposium on Algorithms and Computation (ISAAC 2023) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ISAAC.2023.22 urn:nbn:de:0030-drops-193242 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2023.22 eng https://creativecommons.org/licenses/by/4.0/legalcode