The Parameterized Position Heap of a Trie

Noriki Fujisato; Yuto Nakashima; Shunsuke Inenaga; Hideo Bannai; Masayuki Takeda

doi:10.1007/978-3-030-17402-6_20

The Parameterized Position Heap of a Trie

Noriki Fujisato, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda

Mathematical Informatics

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

4 Citations (Scopus)

Abstract

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.

Original language	English
Title of host publication	Algorithms and Complexity - 11th International Conference, CIAC 2019, Proceedings
Editors	Pinar Heggernes
Publisher	Springer Verlag
Pages	237-248
Number of pages	12
ISBN (Print)	9783030174019
DOIs	https://doi.org/10.1007/978-3-030-17402-6_20
Publication status	Published - 2019
Event	11th International Conference on Algorithms and Complexity, CIAC 2019 - Rome, Italy Duration: May 27 2019 → May 29 2019

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	11485 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	11th International Conference on Algorithms and Complexity, CIAC 2019
Country/Territory	Italy
City	Rome
Period	5/27/19 → 5/29/19

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
Computer Science(all)

Access to Document

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

Cite this

Fujisato, N., Nakashima, Y., Inenaga, S., Bannai, H., & Takeda, M. (2019). The Parameterized Position Heap of a Trie. In P. Heggernes (Ed.), Algorithms and Complexity - 11th International Conference, CIAC 2019, Proceedings (pp. 237-248). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 11485 LNCS). Springer Verlag. https://doi.org/10.1007/978-3-030-17402-6_20

The Parameterized Position Heap of a Trie. / Fujisato, Noriki; Nakashima, Yuto ; Inenaga, Shunsuke et al.
Algorithms and Complexity - 11th International Conference, CIAC 2019, Proceedings. ed. / Pinar Heggernes. Springer Verlag, 2019. p. 237-248 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 11485 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Fujisato, N, Nakashima, Y , Inenaga, S, Bannai, H & Takeda, M 2019, The Parameterized Position Heap of a Trie. in P Heggernes (ed.), Algorithms and Complexity - 11th International Conference, CIAC 2019, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 11485 LNCS, Springer Verlag, pp. 237-248, 11th International Conference on Algorithms and Complexity, CIAC 2019, Rome, Italy, 5/27/19. https://doi.org/10.1007/978-3-030-17402-6_20

Fujisato N, Nakashima Y , Inenaga S, Bannai H, Takeda M. The Parameterized Position Heap of a Trie. In Heggernes P, editor, Algorithms and Complexity - 11th International Conference, CIAC 2019, Proceedings. Springer Verlag. 2019. p. 237-248. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-030-17402-6_20

Fujisato, Noriki ; Nakashima, Yuto ; Inenaga, Shunsuke et al. / The Parameterized Position Heap of a Trie. Algorithms and Complexity - 11th International Conference, CIAC 2019, Proceedings. editor / Pinar Heggernes. Springer Verlag, 2019. pp. 237-248 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{f6a33cd8f34c4f9a83332f604e1772c7,

title = "The Parameterized Position Heap of a Trie",

abstract = "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.",

author = "Noriki Fujisato and Yuto Nakashima and Shunsuke Inenaga and Hideo Bannai and Masayuki Takeda",

note = "Funding Information: YN, SI, HB, MT are respectively supported by JSPS KAKENHI Grant JP18K18002, JP17H01697, JP16H02783, JP18H04098. Publisher Copyright: {\textcopyright} 2019, Springer Nature Switzerland AG.; 11th International Conference on Algorithms and Complexity, CIAC 2019 ; Conference date: 27-05-2019 Through 29-05-2019",

year = "2019",

doi = "10.1007/978-3-030-17402-6_20",

language = "English",

isbn = "9783030174019",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "237--248",

editor = "Pinar Heggernes",

booktitle = "Algorithms and Complexity - 11th International Conference, CIAC 2019, Proceedings",

address = "Germany",

}

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

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 -

The Parameterized Position Heap of a Trie

Abstract

Publication series

Conference

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this