The Parameterized Position Heap of a Trie

Let $Σ$ and $Π$ be disjoint alphabets of respective size $σ$ and $π$. Two strings over $Σ\cup Π$ of equal length are said to parameterized match (p-match) if there is a bijection $f:Σ\cup Π\rightarrow Σ\cup Π$ 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 $\mathcal{T}$ 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 $\mathcal{T}$. In this paper, we propose the parameterized position heap for $\mathcal{T}$ that occupies $O(N)$ space and supports p-matching queries in $O(m \log (σ+ π) + m π+ \mathit{pocc}))$ time, where $m$ is the length of a query pattern $P$ and $\mathit{pocc}$ is the number of paths in $\mathcal{T}$ to report. We also present an algorithm which constructs the parameterized position heap for a given trie $\mathcal{T}$ in $O(N (σ+ π))$ time and working space.