Space-efficient dictionaries for parameterized and order-preserving pattern matching

Let S and S′ be two strings, having the same length, over a totally-ordered alphabet. We consider the following two variants of string matching. ▪ Parameterized Matching: The characters of S and S′ are partitioned into static characters and parameterized characters. The strings are a parameterized match iff the static characters match exactly, and there exists a one-to-one function which renames the parameterized characters in S to those in S′. ▪ Order-Preserving Matching: The strings are an order-preserving match iff for any two integers i, j ∈ [1, |S|], S[i] ≺ S[j] ⇔ S′[i] ≺ S′[j], where ≺ denotes the precedence order of the alphabet. Let P be a collection of d patterns {P1, P2, . . . , Pd} of total length n characters, which are chosen from a totally-ordered alphabet Σ. Given a text T, also over Σ, we consider the dictionary indexing problem under the above definitions of string matching. Specifically, the task is to index P, such that we can report all positions j (called occurrences) where at least one of the patterns Pi ∈ P is a parameterized match (resp. an order-preserving match) with the same-length substring of T starting at j. Previous best-known indexes occupy O(n log n) bits, and can report all occ occurrences in O(|T| log |Σ| + occ) time. We present space-efficient indexes that occupy O(n log |Σ|+d log n) bits, and reports all occ occurrences in O(|T|(log |Σ|+log|Σ| n)+occ) time for parameterized matching, and in O(|T| log n + occ) time for order-preserving matching