Paper Info
Title
DAWGs for parameterized matching: online construction and related indexing structures
Abstract
Two strings $x$ and $y$ over $\Sigma \cup \Pi$ of equal length are said to parameterized match (p-match) if there is a renaming bijection $f:\Sigma \cup \Pi \rightarrow \Sigma \cup \Pi$ that is identity on $\Sigma$ 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 $\Theta(n^2)$ 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 |\Pi| \log (|\Pi| + |\Sigma|))$-time $O(n)$-space algorithm that builds the PDAWG in a left-to-right online manner. We then show that an implicit representation for the PDAWG can be built in $O(n \log (|\Pi| + |\Sigma|))$ time and $O(n)$ space from left to right. 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. We also discuss parameterized compact DAWGs.
Year
DOI
Venue
2020
10.4230/LIPIcs.CPM.2020.26
CPM
DocType
Citations 
PageRank 
Conference
0
0.34
References 
Authors
0
9
Name
Order
Citations
PageRank
Nakashima Katsuhito100.34
Fujisato Noriki200.34
Hendrian Diptarama301.01
Yuto Nakashima45719.52
Ryo Yoshinaka517226.19
Shunsuke Inenaga659579.02
Hideo Bannai762079.87
Ayumi Shinohara893688.28
Masayuki Takeda990279.24