  A parameterized string (p-string) is a string over an alphabet $(\Sigma_{s}
\cup \Sigma_{p})$, where $\Sigma_{s}$ and $\Sigma_{p}$ are disjoint alphabets
for static symbols (s-symbols) and for parameter symbols (p-symbols),
respectively. Two p-strings $x$ and $y$ are said to parameterized match
(p-match) if and only if $x$ can be transformed into $y$ by applying a
bijection on $\Sigma_{p}$ to every occurrence of p-symbols in $x$. The indexing
problem for p-matching is to preprocess a p-string $T$ of length $n$ so that we
can efficiently find the occurrences of substrings of $T$ that p-match with a
given pattern. Extending the Burrows-Wheeler Transform (BWT) based index for
exact string pattern matching, Ganguly et al. [SODA 2017] proposed the first
compact index (named pBWT) for p-matching, and posed an open problem on how to
construct it in compact space, i.e., in $O(n \lg |\Sigma_{s} \cup \Sigma_{p}|)$
bits of space. Hashimoto et al. [SPIRE 2022] partially solved this problem by
showing how to construct some components of pBWTs for $T$ in $O(n
\frac{|\Sigma_{p}| \lg n}{\lg \lg n})$ time in an online manner while reading
the symbols of $T$ from right to left. In this paper, we improve the time
complexity to $O(n \frac{\lg |\Sigma_{p}| \lg n}{\lg \lg n})$. We remark that
removing the multiplicative factor of $|\Sigma_{p}|$ from the complexity is of
great interest because it has not been achieved for over a decade in the
construction of related data structures like parameterized suffix arrays even
in the offline setting. We also show that our data structure can support
backward search, a core procedure of BWT-based indexes, at any stage of the
online construction, making it the first compact index for p-matching that can
be constructed in compact space and even in an online manner.
