The Parameterized Position Heap of a Trie
share
Let Σ and Π be disjoint alphabets of respective size σ and π. Two strings over Σ∪Π of equal length are said to parameterized match (p-match) if there is a bijection f:Σ∪Π→Σ∪Π such that (1) f is identity on Σ 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 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 T. In this paper, we propose the parameterized position heap for T that occupies O(N) space and supports p-matching queries in O(m (σ + π) + m π + pocc)) time, where m is the length of a query pattern P and pocc is the number of paths in T to report. We also present an algorithm which constructs the parameterized position heap for a given trie T in O(N (σ + π)) time and working space.
READ FULL TEXT