Name
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 $Sigma$ and $Pi$ of respective size $sigma$ and $pi$, our construction algorithm runs in $O(n log(sigma + pi))$ time with $O(n)$ space. Our right-to-left parameterized position heaps support pattern matching queries in $O(m log (sigma + pi) + m pi + mathit{pocc}))$ time, where $m$ is the length of a query pattern $P$ and $mathit{pocc}$ is the number of occurrences to report. Our construction and pattern matching algorithms are as efficient as Diptarama et al.u0027s algorithms. |
Year | Venue | Field |
|---|---|---|
2018 | Stringology | Data structure,Discrete mathematics,Combinatorics,Substring,Parameterized complexity,Bijection,Search engine indexing,Heap (data structure),Sigma,Pattern matching,Mathematics |
DocType | Volume | Citations |
Journal | abs/1808.01071 | 0 |
PageRank | References | Authors |
0.34 | 7 | 5 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Noriki Fujisato | 1 | 0 | 1.01 |
| Yuto Nakashima | 2 | 57 | 19.52 |
| Shunsuke Inenaga | 3 | 595 | 79.02 |
| Hideo Bannai | 4 | 620 | 79.87 |
| Masayuki Takeda | 5 | 9 | 13.78 |