文章基本信息

标题：Computing DAWGs and Minimal Absent Words in Linear Time for Integer Alphabets
本地全文：下载
作者：Yuta Fujishige ; Yuki Tsujimaru ; Shunsuke Inenaga 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2016
卷号：58
页码：38:1-38:14
DOI：10.4230/LIPIcs.MFCS.2016.38
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：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.
关键词：string algorithms; DAWGs; suffix trees; minimal absent words