Prague Stringology Conference 2018
Noriki Fujisato, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai and Masayuki Takeda
Right-to-left Online Construction of Parameterized Position Heaps
| Abstract: |
| 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-to-right 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 Π 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(m log(σ + π) + 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. |
| Download paper: |  |
 |
 |
| PostScript | BibTeX reference |