The Parameterized Suffix Tray
share
Let Σ and Π be disjoint alphabets, respectively called the static alphabet and the parameterized alphabet. Two strings x and y over Σ∪Π of equal length are said to parameterized match (p-match) if there exists a renaming bijection f on Σ and Π which is identity on Σ and maps the characters of x to those of y so that the two strings become identical. The indexing version of the problem of finding p-matching occurrences of a given pattern in the text is a well-studied topic in string matching. In this paper, we present a state-of-the-art indexing structure for p-matching called the parameterized suffix tray of an input text T, denoted by 𝖯𝖲𝖳𝗋𝖺𝗒(T). We show that 𝖯𝖲𝖳𝗋𝖺𝗒(T) occupies O(n) space and supports pattern matching queries in O(m + log (σ+π) + 𝑜𝑐𝑐) time, where n is the length of T, m is the length of a query pattern P, π is the number of distinct symbols of |Π| in T, σ is the number of distinct symbols of |Σ| in T and 𝑜𝑐𝑐 is the number of p-matching occurrences of P in T. We also present how to build 𝖯𝖲𝖳𝗋𝖺𝗒(T) in O(n) time from the parameterized suffix tree of T.
READ FULL TEXT