  Let $\Sigma$ and $\Pi$ be disjoint alphabets of respective size $\sigma$ and
$\pi$. Two strings over $\Sigma \cup \Pi$ of equal length are said to
parameterized match (p-match) if there is a bijection $f:\Sigma \cup \Pi
\rightarrow \Sigma \cup \Pi$ such that (1) $f$ is identity on $\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 + \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 (\sigma +
\pi))$ time and working space.
