The Parameterized Position Heap of a Trie

Let $\mathrm{\Sigma }$ and $\mathrm{\Pi }$ be disjoint alphabets of respective size $\sigma$ and $\pi$. Two strings over $\mathrm{\Sigma }\cup \mathrm{\Pi }$ of equal length are said to parameterized match (p-match) if there is a bijection $f:\Sigma \cup \Pi \rightarrow \Sigma \cup \Pi$suchthat(1)$f$isidentityon$\Sigma$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 (\sigma +\pi )+m\pi +pocc))$ time, where $m$ is the length of a query pattern $P$ and $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 (\sigma + \pi))$ time and working space.