We study the problem of matching a determinate pattern against an indeterminate text of the same length n, where each text position is a set of possible characters drawn from an alphabet Σ of size σ. We study this matching problem under the order-preserving and parameterized matching setting. For that, we encode character sets by bit expressions using sum-free sequences. This encoding enables constant-time character comparisons and avoids explicit set operations. We present an optimal 𝒪 (n) time algorithm for order-preserving matching and an 𝒪 (n+ (σₚˣ ⋅ σₚʸ) √σₚˣ + σₚʸ) time algorithm for parameterized matching, where σₚˣ and σₚʸ denote the number of distinct parameterized symbols in the pattern and the text, respectively. The proposed techniques significantly reduce overhead while maintaining exactness, offering practical performance improvements for pattern matching under uncertainty. Additionally, we extend the parameterized matching framework to allow mismatches, for which we present an algorithm with time complexity 𝒪 (σ² n log n + n σ² √σ log (n σ) ).
Faro et al. (Thu,) studied this question.