文章基本信息

标题：DAWGs for Parameterized Matching: Online Construction and Related Indexing Structures
本地全文：下载
作者：Katsuhito Nakashima ; Noriki Fujisato ; Diptarama Hendrian 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2020
卷号：161
页码：26:1-26:14
DOI：10.4230/LIPIcs.CPM.2020.26
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：Two strings x and y over Î£ â^ª Î of equal length are said to parameterized match (p-match) if there is a renaming bijection f:Î£ â^ª Î â' Î£ â^ª Î that is identity on Î£ and transforms x to y (or vice versa). The p-matching problem is to look for substrings in a text that p-match a given pattern. In this paper, we propose parameterized suffix automata (p-suffix automata) and parameterized directed acyclic word graphs (PDAWGs) which are the p-matching versions of suffix automata and DAWGs. While suffix automata and DAWGs are equivalent for standard strings, we show that p-suffix automata can have Î~(nÂ²) nodes and edges but PDAWGs have only O(n) nodes and edges, where n is the length of an input string. We also give O(n Î log ( Î + Î£ ))-time O(n)-space algorithm that builds the PDAWG in a left-to-right online manner. As a byproduct, it is shown that the parameterized suffix tree for the reversed string can also be built in the same time and space, in a right-to-left online manner.
关键词：parameterized matching; suffix trees; DAWGs; suffix automata