DROPS

Artifact

Software

marfra99x/SCER-ISM

Authors: Simone Faro, Dominik Köppl, Thierry Lecroq, and Francesco Pio Marino

Abstract

Cite as

Simone Faro, Dominik Köppl, Thierry Lecroq, Francesco Pio Marino. marfra99x/SCER-ISM (Software, Source Code). Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@misc{dagstuhl-artifact-26165,
   title = {{marfra99x/SCER-ISM}}, 
   author = {Faro, Simone and K\"{o}ppl, Dominik and Lecroq, Thierry and Marino, Francesco Pio},
   note = {Software, swhId: \href{https://archive.softwareheritage.org/swh:1:dir:c33fa1f2fdf35f4030601b03c54ad27d5931dfd0;origin=https://github.com/marfra99x/SCER-ISM;visit=swh:1:snp:516108321a19cbaf1c5afa4642e48da858bea6d1;anchor=swh:1:rev:733c4f4d2ed2b6b639e06205325ad9b699af5602}{\texttt{swh:1:dir:c33fa1f2fdf35f4030601b03c54ad27d5931dfd0}} (visited on 2026-06-08)},
   url = {https://github.com/marfra99x/SCER-ISM},
   doi = {10.4230/artifacts.26165},
}

Document

DOI: 10.4230/LIPIcs.CPM.2026.21

A Bitwise Approach to SCER Matching in Indeterminate Strings

Authors: Simone Faro, Dominik Köppl, Thierry Lecroq, and Francesco Pio Marino

Published in: LIPIcs, Volume 369, 37th Annual Symposium on Combinatorial Pattern Matching (CPM 2026)

Abstract

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 σ)).

Cite as

Simone Faro, Dominik Köppl, Thierry Lecroq, and Francesco Pio Marino. A Bitwise Approach to SCER Matching in Indeterminate Strings. In 37th Annual Symposium on Combinatorial Pattern Matching (CPM 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 369, pp. 21:1-21:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{faro_et_al:LIPIcs.CPM.2026.21,
  author =	{Faro, Simone and K\"{o}ppl, Dominik and Lecroq, Thierry and Marino, Francesco Pio},
  title =	{{A Bitwise Approach to SCER Matching in Indeterminate Strings}},
  booktitle =	{37th Annual Symposium on Combinatorial Pattern Matching (CPM 2026)},
  pages =	{21:1--21:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-420-8},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{369},
  editor =	{Bille, Philip and Prezza, Nicola},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2026.21},
  URN =		{urn:nbn:de:0030-drops-259470},
  doi =		{10.4230/LIPIcs.CPM.2026.21},
  annote =	{Keywords: string matching, indeterminate strings, SCER matching}
}

Search Results

Documents authored by Lecroq, Thierry

marfra99x/SCER-ISM

Abstract

Cite as

A Bitwise Approach to SCER Matching in Indeterminate Strings

Abstract

Cite as

Thanks for your feedback!

Could not send message