Paper Info
Title
Parameterized DAWGs: Efficient constructions and bidirectional pattern searches
Abstract
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 Θ(n2) nodes and edges but PDAWGs have only O(n) nodes and edges, where n is the length of an input string. We also give an 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. This duality also leads us to two further efficient algorithms for p-matching: Given the parameterized suffix tree for the reversal T‾ of the input string T, one can build the PDAWG of T in O(n) time in an offline manner; One can perform bidirectional p-matching in O(mlog⁡(|Π|+|Σ|)+occ) time using O(n) space, where m denotes the pattern length and occ is the number of pattern occurrences in the text T.
Year
DOI
Venue
2022
10.1016/j.tcs.2022.09.008
Theoretical Computer Science
Keywords
DocType
Volume
Parameterized matching,Suffix trees,DAWGs,Suffix automata
Journal
933
ISSN
Citations 
PageRank 
0304-3975
0
0.34
References 
Authors
0
9
Name
Order
Citations
PageRank
Katsuhito Nakashima100.34
Noriki Fujisato200.34
Diptarama Hendrian300.34
Yuto Nakashima401.35
Ryo Yoshinaka517226.19
Shunsuke Inenaga659579.02
Hideo Bannai762079.87
Ayumi Shinohara893688.28
Masayuki Takeda9913.78