Title: Position Heaps for Parameterized Strings,
Abstract: We propose a new indexing structure for parameterized strings, called
parameterized position heap. Parameterized position heap is applicable for
parameterized pattern matching problem, where the pattern matches a substring
of the text if there exists a bijective mapping from the symbols of the pattern
to the symbols of the substring. We propose an online construction algorithm of
parameterized position heap of a text and show that our algorithm runs in
linear time with respect to the text size. We also show that by using
parameterized position heap, we can find all occurrences of a pattern in the
text in linear time with respect to the product of the pattern size and the
alphabet size.