2026-07-21T19:38:20Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:25947 2026-06-23T13:12:36Z ddc:004 open_access

A Bitwise Approach to SCER Matching in Indeterminate Strings Faro, Simone Köppl, Dominik Lecroq, Thierry Marino, Francesco Pio string matching indeterminate strings SCER matching 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+(σ_p^x ⋅ σ_p^y) √{σ_p^x + σ_p^y}) time algorithm for parameterized matching, where σ_p^x and σ_p^y 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 σ)). Schloss Dagstuhl – Leibniz-Zentrum für Informatik Simone Faro and Dominik Köppl and Thierry Lecroq and Francesco Pio Marino 2026 Is Part Of LIPIcs, Volume 369, 37th Annual Symposium on Combinatorial Pattern Matching (CPM 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.CPM.2026.21 urn:nbn:de:0030-drops-259470 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2026.21 eng https://creativecommons.org/licenses/by/4.0/legalcode