  The parameterized matching problem is a variant of string matching, which is
to search for all parameterized occurrences of a pattern $P$ in a text $T$. In
considering matching algorithms, the combinatorial natures of strings,
especially periodicity, play an important role. In this paper, we analyze the
properties of periods of parameterized strings and propose a generalization of
Galil and Seiferas's exact matching algorithm (1980) into parameterized
matching, which runs in $O(\pi|T|+|P|)$ time and $O(\log{|P|}+|{\rm\Pi}|)$
space in addition to the input space, where ${\rm\Pi}$ is the parameter
alphabet and $\pi$ is the number of parameter characters appearing in $P$ plus
one.
