TY - GEN

T1 - The Parameterized Position Heap of a Trie

AU - Fujisato, Noriki

AU - Nakashima, Yuto

AU - Inenaga, Shunsuke

AU - Bannai, Hideo

AU - Takeda, Masayuki

N1 - Funding Information:
YN, SI, HB, MT are respectively supported by JSPS KAKENHI Grant JP18K18002, JP17H01697, JP16H02783, JP18H04098.
Publisher Copyright:
© 2019, Springer Nature Switzerland AG.

PY - 2019

Y1 - 2019

N2 - Let and be disjoint alphabets of respective size and. Two strings over of equal length are said to parameterized match (p-match) if there is a bijection such that (1) f is identity on and (2) f maps the characters of one string to those of the other string so that the two strings become identical. We consider the p-matching problem on a (reversed) trie and a string pattern P such that every path that p-matches P has to be reported. Let N be the size of the given trie. In this paper, we propose the parameterized position heap for that occupies O(N) space and supports p-matching queries in time, where m is the length of a query pattern P and is the number of paths in to report. We also present an algorithm which constructs the parameterized position heap for a given trie in time and working space.

AB - Let and be disjoint alphabets of respective size and. Two strings over of equal length are said to parameterized match (p-match) if there is a bijection such that (1) f is identity on and (2) f maps the characters of one string to those of the other string so that the two strings become identical. We consider the p-matching problem on a (reversed) trie and a string pattern P such that every path that p-matches P has to be reported. Let N be the size of the given trie. In this paper, we propose the parameterized position heap for that occupies O(N) space and supports p-matching queries in time, where m is the length of a query pattern P and is the number of paths in to report. We also present an algorithm which constructs the parameterized position heap for a given trie in time and working space.

UR - http://www.scopus.com/inward/record.url?scp=85066911091&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85066911091&partnerID=8YFLogxK

U2 - 10.1007/978-3-030-17402-6_20

DO - 10.1007/978-3-030-17402-6_20

M3 - Conference contribution

AN - SCOPUS:85066911091

SN - 9783030174019

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 237

EP - 248

BT - Algorithms and Complexity - 11th International Conference, CIAC 2019, Proceedings

A2 - Heggernes, Pinar

PB - Springer Verlag

T2 - 11th International Conference on Algorithms and Complexity, CIAC 2019

Y2 - 27 May 2019 through 29 May 2019

ER -