A Bitwise Approach to SCER Matching in Indeterminate Strings

The problem of string matching is a foundational challenge in theoretical computer science, with widespread applications in areas such as bioinformatics, text retrieval, and pattern recognition [5, 12]. In its classical formulation, the problem assumes deterministic input, where each position in a string contains a single, fixed character drawn from a finite alphabet. Under this assumption, a match between two strings is defined as exact equality at every position.

However, in many real-world scenarios, this assumption does not hold. Strings may exhibit uncertainty – so-called indeterminate strings – in which some positions contain a set of possible characters rather than a unique one. This type of uncertainty naturally arises in biological sequence analysis (e.g., ambiguous nucleotides), noisy or corrupted text data, and symbolic pattern recognition, motivating the need for more expressive and robust matching models [19].

A standard approach to matching indeterminate strings is to interpret a match as the existence of a consistent assignment of characters to each position such that the two strings become identical. When the alphabet is small, an efficient implementation strategy is to encode characters and character classes using bit-parallelism. In this setting, the alphabet $\mathrm{\Sigma }$ is mapped to a set of bit masks, and each symbol is represented as a binary vector indicating the presence or absence of characters. For instance, in the DNA alphabet $\{A,C,G,T\}$, each character can be encoded using a 4-bit mask, and indeterminate symbols correspond to bitwise combinations of these masks. This representation allows character comparisons to be performed using constant-time bitwise operations, making it highly effective in practice [17].

An alternative encoding strategy is based on number-theoretic techniques, where each character is associated with a distinct prime number and indeterminate symbols are represented as products of primes. Matching can then be tested via greatest common divisor (GCD) computations. While conceptually elegant, this approach is generally impractical due to the high computational cost of arithmetic operations and the exponential growth of prime products, restricting its applicability to very small alphabets [6].

Beyond exact matching, indeterminate string matching has been studied under more general equivalence relations that capture richer notions of similarity. A particularly important class is that of substring consistent equivalence relations (SCERs). An equivalence relation $\approx$ is said to be substring consistent if, for any two strings $x$ and $y$ such that $x\approx y$, it holds that (i) $|x|=|y|$, and (ii) $x[i..j]\approx y[i..j]$ for all substrings. This property ensures that matching is preserved under substring extraction and is satisfied by several well-known matching paradigms.

Notable examples of SCER-based matching include parameterized matching, order-preserving matching, and variants of palindrome pattern matching. These models have been widely studied due to their applicability in domains where structural or relative relationships between symbols are more important than their exact identities.

This section introduces the notation, definitions, and mathematical foundations required for our approach. We begin by defining indeterminate strings and their matching criteria, followed by an introduction to sum-free sequences (an increasing sequence of numbers is sum-free if no term $a_k$ can be expressed as the sum of any subset of its preceding terms $a_1,\mathrm{\dots },a_{k-1}$; e.g., the powers of two $1,2,4,8,\mathrm{\dots }$) and their computational properties, which form the basis for our efficient encoding and search mechanisms.

Let $\mathrm{\Sigma }$ be a finite and totally ordered alphabet. A determinate string $u$ of length $n$ is defined as: $u=u[1]u[2]\mathrm{\dots }u[n],u[i]\in \mathrm{\Sigma },\forall i\in [1,n].$ An indeterminate string $w$ of length $n$ is a string whose symbols are taken from the power set of $\mathrm{\Sigma }$, that is $w=w[1]w[2]\mathrm{\dots }w[n],w[i]\subseteq \mathrm{\Sigma },\forall i\in [1,n].$ Since each position can be a singleton set, indeterminate strings are a generalization of determinate strings.

We define assignment of an indeterminate string $y$ is a string $\widehat{y}$ such that $\widehat{y}[i]\in y[i]$.

For an indeterminate symbol $w[i]\subseteq \mathrm{\Sigma }$, we denote its elements in increasing order as Equivalently, each element can be characterized as $w[i,j]=\{c\in w[i]:|\{d\in w[i]:d\le c\}|=j\},$ so in particular $w[i,1]$ is the minimum of $w[i]$. This notation allows us to explicitly refer to the $j$-th element of $w[i]$.

This perspective also highlights a connection with 2D-strings [3], since each position of an indeterminate string can be regarded as a (sorted) list of possible symbols.

A common technique for handling indeterminate strings is to use a bitwise encoding, where each character position is represented by a bitmask indicating which symbols are present [18]. This allows set operations, such as membership testing, to be performed efficiently. Specifically, each symbol $a\in \mathrm{\Sigma }$ is assigned a unique bit position, and the presence of a set of characters at a given position is represented as a bitwise OR operation over their corresponding bit values. Let $\mathrm{\Sigma }=\{a_1,a_2,\mathrm{\dots },a_{\sigma }\}$ be an alphabet of size $\sigma$. We define a mapping $ℳ:\mathrm{\Sigma }\to \mathbb{N}$ that assigns a distinct power of two to each symbol: $ℳ(a_i)=2^{i-1},\forall i\in [1,\sigma ]$, similarly given a determinate string $y[1..n]$ we define $ℳ(y)=[ℳ(y[1]),ℳ(y[2]),\mathrm{\dots },ℳ(y[n])]$. Then, an indeterminate letter $w[i]\subseteq \mathrm{\Sigma }$ is encoded by the mapping $\overline{ℳ}:2^{\mathrm{\Sigma }}\to \mathbb{N}$ as: $\overline{ℳ}(w[i])={\sum }_{a\in w[i]}ℳ(a)$, i.e. the $k$-th bit is set to $1$ if and only if the $k$-th symbol of $\mathrm{\Sigma }$ is contained in $w[i]$. Likewise, we can generalize $\overline{ℳ}$ to strings. Using this encoding, a match between an indeterminate text and an indeterminate pattern at position $j$ can be determined using a bitwise AND operation: $\overline{ℳ}(x[i])\cap \overline{ℳ}(y[j+i-1])\ne 0,\forall i\in [1,m].$ This formulation allows for fast comparisons and eliminates the need for explicit set intersection checks.

We define the symbol $\wedge$ to denote the bitwise AND operation between two binary strings of equal length. Given $a,b\in {\{0,1\}}^n$, the result of $a\wedge b$ is the binary string $c\in {\{0,1\}}^n$ such that $c_i=a_i\cdot b_i$ for all $i\in [1,n]$.

Throughout this work, we assume the standard word-RAM model with word size $w=\mathrm{\Omega }(\log n)$. Under this assumption, bitwise operations on machine words can be performed in constant time when the alphabet size $\sigma$ is bounded by $w$. For larger alphabets, an additional $\log \sigma$ factor is required to account for set operations.

Let $x=x[1]x[2]\mathrm{\dots }x[n]$ and $y=y[1]y[2]\mathrm{\dots }y[n]$ be two strings of equal length, drawn from a finite ordered alphabet $\mathrm{\Sigma }=\{a_1,a_2,\mathrm{\dots },a_{\sigma }\}$ of size $\sigma$. Each symbol $a_i$ is assigned a unique numerical value through the mapping: $ℳ:\mathrm{\Sigma }\to \mathbb{N},ℳ(a_i)=2^{i-1},\text{for }1\le i\le \sigma .$ This encoding ensures that each determinate character is represented as a distinct power of two.

For an indeterminate string $y$, given the presence of indeterminate positions $i$, where a character may belong to a subset of $\mathrm{\Sigma }$, the numerical representation is given by: $\overline{ℳ}(y[i])={\sum }_{c\in y[i]}ℳ(c).$

This representation ensures that determinate characters correspond to single powers of two, while indeterminate positions are encoded as sums of distinct powers of two. Since the powers of two form a sum-free sequence, each distinct subset of characters maps to a unique integer representation. This property allows for efficient encoding and comparison of indeterminate positions using bitwise operations. Thus, in this model, the string $x$ is determinate, which means that each position contains exactly one character, while $y$ is indeterminate, allowing each position to contain a subset of characters from $\mathrm{\Sigma }$.

An order-preserving match occurs when the text $y$ matches $x$, such that the relative order of the characters in $x$ is preserved in $y$. This formulation enables pattern matching in settings where the uncertainty in $y$ must be taken into account while maintaining structural consistency.

To formalize this notion, we define a rank function $\rho :{\mathrm{\Sigma }}^n\to {[1..n]}^n$ that assigns an order-preserving rank to each character of a string. A ranking is order-preserving if the ranked string order-preserving matches with the original string. The rank function $\rho (x)$ is defined as $\rho (x)=(r_1,r_2,\mathrm{\dots },r_n),\text{where}{r}_i=\left|\{j\mid x[j]\le x[i]\}\right|.$ $\rho (x)$ defines a permutation, whose inverse $\rho {(x)}^{-1}=[p_1,\mathrm{\dots },p_n]$ gives the indices of $x$ in increasing order with respect to their ranks.

Since $\rho$ preserves order relations, determining an order-preserving match in our setting reduces to verifying whether the ranks of the positions $\rho {(x)}^{-1}=\rho {(\widehat{y})}^{-1}$ is the same, for some assignment $\widehat{y}$ of $y$. The algorithm processes the text $y$ according to the order induced by the rank vector $\rho (x)$ of the pattern $x$. For each position $i$ in this order, it checks whether $y[i]$ is determinate or indeterminate.

Let $x$ be a determinate string drawn from an alphabet ${\mathrm{\Sigma }}^x$ of size ${\sigma }^x$, partitioned into two disjoint subsets: a fixed alphabet ${\mathrm{\Sigma }}_s$ and a parameterized alphabet ${\mathrm{\Sigma }}_p^x$, such that ${\mathrm{\Sigma }}^x={\mathrm{\Sigma }}_s\cup {\mathrm{\Sigma }}_p^x$, with $|{\mathrm{\Sigma }}_s|={\sigma }_s$ and $|{\mathrm{\Sigma }}_p^x|={\sigma }_p^x$.

Let $y$ be an indeterminate string of the same length as $x$, drawn from an alphabet ${\mathrm{\Sigma }}^y$ of size ${\sigma }^y$, also partitioned into the same fixed alphabet ${\mathrm{\Sigma }}_s$ and a parameterized alphabet ${\mathrm{\Sigma }}_p^y$, such that ${\mathrm{\Sigma }}^y={\mathrm{\Sigma }}_s\cup {\mathrm{\Sigma }}_p^y$, with $|{\mathrm{\Sigma }}_p^y|={\sigma }_p^y$.

Parameterized matching allows dynamic mappings from characters in $x$ that belong to ${\mathrm{\Sigma }}_p^x$ to characters in $y$ that belong to ${\mathrm{\Sigma }}_p^y$, provided the structural consistency of $x$ is preserved. Thus, to define an injective function from ${\mathrm{\Sigma }}_p^x$ to ${\mathrm{\Sigma }}_p^y$, it is necessary that ${\sigma }_p^x\ge {\sigma }_p^y$.

Additionally, we consider that $y$ may include indeterminate positions, where each $y[i]$ represents a subset of ${\mathrm{\Sigma }}^y$. To support efficient matching under these conditions, we use a bitwise encoding scheme in which each character is represented by a bitmask. This allows filtering via bitwise operations.

Initially, each parameterized character $c\in {\mathrm{\Sigma }}_p^x$ is assigned a bitmask value: $\text{mask}[c]=2^{{\sigma }_p^y}-1$ which permits it to map to any symbol in ${\mathrm{\Sigma }}_p^y$. The algorithm proceeds by scanning the string $x$ and refining these bitmasks using the corresponding entries in $y$. When $y[i]$ is a fixed character, it must match exactly $x[i]$; if not, the match fails immediately. If $y[i]$ is parameterized, the characters in $y[i]$ are encoded as a bitmask, and this is intersected with the current $\text{mask}[x[i]]$ via: $\text{mask}[x[i]]=\text{mask}[x[i]]\wedge ℳ(y[i]),$ removing any characters from the mapping that do not appear in $y[i]$.

A parameterized match is only possible if every character in ${\mathrm{\Sigma }}_p^x$ retains at least one valid mapping after filtering, i.e., $\text{mask}[c]>0$ for all $c\in {\mathrm{\Sigma }}_p^x$. However, this condition does not guarantee that a valid one-to-one mapping exists.

To enforce uniqueness, we reduce the problem to a bipartite graph matching instance. We construct a bipartite graph $G=(U,W,E)$, where $U$ is the set of parameterized characters in the pattern $x$, and $W$ is the set of parameterized characters in the text $y$. We assume $|V|=|U|+|W|$. An edge exists between $u\in U$ and $w\in W$ if the bitmask associated with $u$ contains a $1$ at the position corresponding to $w$, indicating compatibility.

A valid match exists if and only if there is a maximum matching in $G$ that covers all nodes in $U$, ensuring a unique assignment for each parameterized symbol in the pattern. This can be efficiently computed using the Hopcroft-Karp algorithm, which runs in time $𝒪(|E|\sqrt{|V|})$ in the general case [14].

In our setting, we have $|U|={\sigma }_p^x$ and $|W|={\sigma }_p^y$, so the total number of vertices is $|V|=|U|+|W|={\sigma }_p^x+{\sigma }_p^y$. The number of edges $|E|$ is determined by the bitmask encoding and is upper-bounded by ${\sigma }_p^x\cdot {\sigma }_p^y$ in the case of full compatibility.

Therefore, the Hopcroft-Karp algorithm runs in time $𝒪(|E|\sqrt{{\sigma }_p^x+{\sigma }_p^y})$ in the general case, and up to $𝒪(({\sigma }_p^x\cdot {\sigma }_p^y)\sqrt{{\sigma }_p^x+{\sigma }_p^y})$ in the worst case. Notably, in the fully dense case where $G$ is a complete bipartite graph, the classical bound from Hopcroft and Karp applies, yielding a worst-case complexity of $𝒪({|V|}^{2.5})$ [14].

In practice, however, this step is often significantly faster due to the sparsity of the compatibility graph and the typically low degree of ambiguity. The pseudo-code for this procedure is provided in Algo. 2, which we call the Parameterized Indeterminate String Matching (PISM).

We now analyze the computational complexity of the proposed parameterized matching algorithm. The procedure consists of three main steps: filtering the parameterized symbols using bitwise operations, constructing a bipartite graph based on the remaining valid mappings, and computing a maximum matching to enforce one-to-one assignments.

The filtering phase takes $𝒪(n)$ time due to constant-time bitwise operations per position. Constructing the bipartite graph from the bitmask representations requires $𝒪({\sigma }_p^x{\sigma }_p^y)$ time in the worst case. The final matching step, performed via the Hopcroft–Karp algorithm, runs in $𝒪(({\sigma }_p^x\cdot {\sigma }_p^y)\sqrt{{\sigma }_p^x+{\sigma }_p^y})$ time.

Consequently, the overall time complexity of the algorithm is: $𝒪(n+({\sigma }_p^x\cdot {\sigma }_p^y)\sqrt{{\sigma }_p^x+{\sigma }_p^y})$. The space complexity depends primarily on the representation of the bipartite graph. Using an adjacency matrix yields a worst-case space usage of $𝒪({\sigma }_p^x{\sigma }_p^y)$. Alternatively, an adjacency list may be employed to reduce space consumption in sparse instances, although the asymptotic bound remains the same.

Algorithm 2 implements parameterized matching between a determinate pattern $x$ and an indeterminate text $y$ under the alphabets ${\mathrm{\Sigma }}^x={\mathrm{\Sigma }}_s\cup {\mathrm{\Sigma }}_p^x$ and ${\mathrm{\Sigma }}^y={\mathrm{\Sigma }}_s\cup {\mathrm{\Sigma }}_p^y$. It first initializes masks for all parameterized symbols (lines 2–3). Then, in the presence of indeterminate characters, it updates these masks based on the observed matches between $x$ and $y$ (line 9). Finally, a bipartite graph is constructed from the masks (line 10), and the existence of a full matching (line 11) determines whether $x$ matches $y$ under the parameterized model.

The problem of parameterized matching with mismatches [1] has been recently revisited by Saha et al. [20]. In their formulation, given two deterministic strings $x$ and $y$ of equal length $n$, a weighted bipartite graph $G=(U\cup V,E)$ is constructed, where $U=V={\mathrm{\Sigma }}_p$. Each edge $(a,b)\in E$ is weighted by the number of positions $i$ such that $x_i=a$ and $y_i=b$. The minimum number of mismatches is then $n_p-\mathrm{mwm}(G),$ where $\mathrm{mwm}(G)$ denotes the maximum weighted matching of $G$ and $n_p=\left|\{i\in [1..n]\mid x[i]\in {\mathrm{\Sigma }}_p^x\}\right|$. This reduction enables efficient algorithms for approximate parameterized matching, including cases with a bounded number of mismatches. We now extend this framework to the case of a determinate string $x$ and an indeterminate string $y$, formally defined as follows:

In the exact setting, we initialized each mask with all ones and progressively refined it via bitwise AND operations, thereby filtering out incompatible candidates until only consistent bijections remained. To allow mismatches, this logic is inverted: since each $y[i]$ is a set of possible symbols, the goal is to accumulate all compatibilities rather than restrict them. We therefore initialize every parameterized symbol with an all-zeros mask and update it by bitwise OR: $\text{mask}[x[i]]=\text{mask}[x[i]]\vee ℳ(y[i]),$ so that all candidates compatible with $y[i]$ are preserved. The OR-masks specify adjacency in the bipartite graph but not edge multiplicities. To capture frequencies, we introduce an auxiliary array $\mu$ of size $|{\mathrm{\Sigma }}_p|$ such that $\mu [c]=\left|\{i\mid c\in y[i]\}\right|,$ counting how many times $c$ appears in the subsets of $y$. Consequently, for each pair $(a,b)\in {\mathrm{\Sigma }}_p^x\times {\mathrm{\Sigma }}_p^y$, the weight of edge $(a,b)$ equals the number of positions $i$ with $x[i]=a$ and $b\in y[i]$. This generalizes the deterministic case, where all edges had unit weight. The resulting bipartite graph is thus defined by OR-masks (adjacency) and the $\mu$ array (weights). The maximum weighted matching of this graph again determines the optimal alignment, and the minimum number of mismatches is $n_p-\mathrm{mwm}(G).$

Since only the edge weights differ while the graph structure is preserved, the algorithm of Saha et al. [20] remains directly applicable, with time complexity $𝒪({\sigma }^{2}n\log n+n{\sigma }^2\sqrt{\sigma }\log (n\sigma ))$. Constructing the OR-masks and $\mu$ requires only $𝒪(n)$ preprocessing, so the dominant cost remains the FFT-based polynomial multiplication [4] and the maximum weighted bipartite matching, yielding the same asymptotic complexity as in the deterministic case.

The proposed algorithms were implemented in C.¹¹1Source code available at https://github.com/marfra99x/SCER-ISM. Experiments were conducted on a MacBook Pro equipped with a 2.7 GHz Intel Core i7-8559U (4 cores), with 16 GB RAM. All algorithms were compiled using the -O3 optimization flag.

Performance was measured in terms of search execution time (milliseconds) on randomly generated texts. We report two complementary experiments, shown as the two plots of Fig. 1.

Within the context of order-preserving pattern matching (OPPM), we compare two approaches: OLD, referring to the algorithm proposed by Henriques et al. [13]; and NEW, representing the bitwise-compatible method introduced in this work. For the parameterized string matching setting, we evaluate the PISM algorithm, designed to support efficient bit-parallelism in handling variable symbol classes and the Mismatches Parameterized Indeterminate String Matching (MPISM)²²2Although MPISM is described in the paper using a fast FFT-based procedure, in our experiments we employ the Hungarian algorithm [16] for maximum weighted bipartite matching, as it offers a simpler and more straightforward implementation. Nonetheless, the FFT-based approach outlined in the paper could yield faster results.. In the left plot, the x–axis varies according to the specific setting. For OPPM, it represents the number of uncertain characters per position, denoted by $r$. For PISM, it corresponds to the size of the parameterized alphabet of the text, ${\sigma }_p^y$, which captures the diversity of symbol classes. For MPISM, we fix three different sizes of the parameterized alphabet $|{\mathrm{\Sigma }}_p|=\{2,8,32\}$ (small, medium and large) and instead vary the number of allowed mismatches in the input to assess performance. Additionally, in the right plot, all parameters are fixed and only the text length $n$ varies, taking values between ${10}^4$ and ${10}^7$. The results in Fig. 1 show a substantial and consistent speedup of NEW over OLD across all tested regimes. On average, our method outperforms the prior state-of-the-art by over $92\%$, confirming the benefits of the bit-parallel encoding. PISM maintains competitive performance while MPISM displays the expected growth as ${\sigma }_p^y$ and $n$ increase, reflecting the underlying matching complexities.

These results confirm the effectiveness of our algorithms not only in theoretical terms but also in practice, particularly for large-scale texts where traditional set-based comparisons become a performance bottleneck. The combination of sum-free sequence encoding and greedy selection strategies leads to measurable improvements in runtime performance.

In this work, we introduced efficient algorithms for matching a determinate pattern against an indeterminate text under two notable substring consistent equivalence relations (SCERs): order-preserving and parameterized matching. By leveraging a bitwise-compatible encoding based on sum-free sequences, our approach enables constant-time character comparisons and compact set representations. The resulting techniques achieve an optimal time complexity of $O(n)$ for order-preserving matching and $𝒪(n+({\sigma }_p^x\cdot {\sigma }_p^y)\sqrt{{\sigma }_p^x+{\sigma }_p^y})$ for parameterized matching, where ${\sigma }_p^x$ and ${\sigma }_p^y$ denote the number of distinct parameterized symbols, in the pattern and text, respectively.

The efficiency of our approach can be further enhanced through pre-sampling strategies. Sampling techniques have proven effective in reducing redundant search spaces and filtering unpromising regions in various exact and approximate matching tasks [8]. Applying such techniques in the context of indeterminate matching may enable early pruning and tighter complexity bounds, especially in large-scale or high-ambiguity datasets.

In addition, we extended the parameterized framework to handle mismatches in the presence of indeterminate positions, we showed that the construction naturally reduces to the same weighted bipartite graph formulation of Saha et al. [20]. As a result, their FFT-based computation and matching algorithm carry over unchanged, with only a linear preprocessing overhead. This demonstrates that approximate parameterized matching can also be tackled efficiently in the indeterminate setting, further broadening the scope of tractable problems under SCERs. Future directions include extending this asymmetric framework to other SCER models, integrating adaptive sampling mechanisms, and optimizing for real-time or streaming contexts where input uncertainty dynamically evolves.