2026-07-22T19:23:43Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:12151 2024-03-06T10:49:25Z ddc:004 open_access

DAWGs for Parameterized Matching: Online Construction and Related Indexing Structures Nakashima, Katsuhito Fujisato, Noriki Hendrian, Diptarama Nakashima, Yuto Yoshinaka, Ryo Inenaga, Shunsuke Bannai, Hideo Shinohara, Ayumi Takeda, Masayuki parameterized matching suffix trees DAWGs suffix automata 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Katsuhito Nakashima and Noriki Fujisato and Diptarama Hendrian and Yuto Nakashima and Ryo Yoshinaka and Shunsuke Inenaga and Hideo Bannai and Ayumi Shinohara and Masayuki Takeda 2020 Is Part Of LIPIcs, Volume 161, 31st Annual Symposium on Combinatorial Pattern Matching (CPM 2020) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.CPM.2020.26 urn:nbn:de:0030-drops-121512 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2020.26 eng https://creativecommons.org/licenses/by/3.0/legalcode