TY - GEN

T1 - Right-to-left online construction of parameterized position heaps

AU - Fujisato, Noriki

AU - Nakashima, Yuto

AU - Inenaga, Shunsuke

AU - Bannai, Hideo

AU - Takeda, Masayuki

N1 - Publisher Copyright:
© Proceedings of the Prague Stringology Conference, PSC 2018. All rights reserved.

PY - 2018

Y1 - 2018

N2 - Two strings of equal length are said to parameterized match if there is a bijection that maps the characters of one string to those of the other string, so that two strings become identical. The parameterized pattern matching problem is, given two strings T and P, to find the occurrences of substrings in T that parameterized match P. Diptarama et al. [Position Heaps for Parameterized Strings, CPM 2017] proposed an indexing data structure called parameterized position heaps, and gave a left-toright online construction algorithm. In this paper, we present a right-to-left online construction algorithm for parameterized position heaps. For a text string T of length n over two kinds of alphabets Σand II of respective size σ and π, our construction algorithm runs in O(n log(σ+π)) time with O(n) space. Our right-to-left parameterized position heaps support pattern matching queries in O(mlog(σ+π)+mπ+pocc)) time, where m is the length of a query pattern P and pocc is the number of occurrences to report. Our construction and pattern matching algorithms are as efficient as Diptarama et al.'s algorithms.

AB - Two strings of equal length are said to parameterized match if there is a bijection that maps the characters of one string to those of the other string, so that two strings become identical. The parameterized pattern matching problem is, given two strings T and P, to find the occurrences of substrings in T that parameterized match P. Diptarama et al. [Position Heaps for Parameterized Strings, CPM 2017] proposed an indexing data structure called parameterized position heaps, and gave a left-toright online construction algorithm. In this paper, we present a right-to-left online construction algorithm for parameterized position heaps. For a text string T of length n over two kinds of alphabets Σand II of respective size σ and π, our construction algorithm runs in O(n log(σ+π)) time with O(n) space. Our right-to-left parameterized position heaps support pattern matching queries in O(mlog(σ+π)+mπ+pocc)) time, where m is the length of a query pattern P and pocc is the number of occurrences to report. Our construction and pattern matching algorithms are as efficient as Diptarama et al.'s algorithms.

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

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

M3 - Conference contribution

AN - SCOPUS:85066903210

T3 - Proceedings of the Prague Stringology Conference, PSC 2018

SP - 91

EP - 102

BT - Proceedings of the Prague Stringology Conference, PSC 2018

A2 - Holub, Jan

A2 - Zdarek, Jan

PB - Prague Stringology Club

T2 - 22nd Prague Stringology Conference, PSC 2018

Y2 - 27 August 2018 through 28 August 2018

ER -