2026-08-10T11:49:37Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:6452 2024-03-06T10:38:18Z ddc:004 open_access

Computing DAWGs and Minimal Absent Words in Linear Time for Integer Alphabets Fujishige, Yuta Tsujimaru, Yuki Inenaga, Shunsuke Bannai, Hideo Takeda, Masayuki string algorithms DAWGs suffix trees minimal absent words The directed acyclic word graph (DAWG) of a string y is the smallest (partial) DFA which recognizes all suffixes of y and has only O(n) nodes and edges. We present the first O(n)-time algorithm for computing the DAWG of a given string y of length n over an integer alphabet of polynomial size in n. 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. As an application to our O(n)-time DAWG construction algorithm, we show that the set MAW(y) of all minimal absent words of y can be computed in optimal O(n + |MAW(y)|) time and O(n) working space for integer alphabets. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Yuta Fujishige and Yuki Tsujimaru and Shunsuke Inenaga and Hideo Bannai and Masayuki Takeda 2016 Is Part Of LIPIcs, Volume 58, 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.MFCS.2016.38 urn:nbn:de:0030-drops-64528 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2016.38 eng https://creativecommons.org/licenses/by/3.0/legalcode