TY - GEN
T1 - DAWGs for Parameterized Matching
T2 - 31st Annual Symposium on Combinatorial Pattern Matching, CPM 2020
AU - Nakashima, Katsuhito
AU - Fujisato, Noriki
AU - Hendrian, Diptarama
AU - Nakashima, Yuto
AU - Yoshinaka, Ryo
AU - Inenaga, Shunsuke
AU - Bannai, Hideo
AU - Shinohara, Ayumi
AU - Takeda, Masayuki
N1 - Funding Information:
Funding Diptarama Hendrian: JSPS KAKENHI Grant Number JP19K20208. Yuto Nakashima: JSPS KAKENHI Grant Number JP18K18002. Ryo Yoshinaka: JSPS KAKENHI Grant Number JP18H04091.
Funding Information:
Shunsuke Inenaga: JSPS KAKENHI Grant Number JP17H01697, JST PRESTO Grant Number JPMJPR1922. Hideo Bannai: JSPS KAKENHI Grant Numbers JP16H02783, JP20H04141. Ayumi Shinohara: JSPS KAKENHI Grant Number JP15H05706. Masayuki Takeda: JSPS KAKENHI Grant Number JP18H04098.
Publisher Copyright:
© 2020 Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. All rights reserved.
PY - 2020/6/1
Y1 - 2020/6/1
N2 - 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 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. 2012 ACM Subject Classification Theory of computation ! Pattern matching.
AB - 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 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. 2012 ACM Subject Classification Theory of computation ! Pattern matching.
KW - Dawgs
KW - Parameterized matching
KW - Suffix automata
KW - Suffix trees
UR - http://www.scopus.com/inward/record.url?scp=85088366317&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85088366317&partnerID=8YFLogxK
U2 - 10.4230/LIPIcs.CPM.2020.26
DO - 10.4230/LIPIcs.CPM.2020.26
M3 - Conference contribution
AN - SCOPUS:85088366317
T3 - Leibniz International Proceedings in Informatics, LIPIcs
BT - 31st Annual Symposium on Combinatorial Pattern Matching, CPM 2020
A2 - Gortz, Inge Li
A2 - Weimann, Oren
PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
Y2 - 17 June 2020 through 19 June 2020
ER -