2026-09-05T06:57:24Z https://drops.dagstuhl.de/oai

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

Set Parameterized Matching via Multi-Layer Hashing Lewenstein, Moshe Porat, Ely Set Parameterized Matching Pattern Matching Randomized Algorithms Hashing Parameterized Matching We study the set parameterized matching problem, a generalization of the classical parameterized matching problem introduced by Baker [Baker, 1993; Baker, 1997]. In set parameterized matching, both the pattern and text are sequences where each position contains a set of characters rather than a single character. Two set-strings parameterized match if there exists a bijection between their alphabets that maps one to the other set-wise. Boussidan [Aaron Boussidan, 2025] introduced this problem for the case of equal-length set-strings. We present a randomized algorithm running in O(N + M) time with high probability, where N is the text size and M is the pattern size. Our approach employs a novel three-layer hashing scheme based on Karp-Rabin fingerprinting that addresses the challenges of (1) the size blowup in representations of the problem, (2) set-to-set matching, and (3) the dynamic nature of encodings of text substrings during pattern scanning. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Moshe Lewenstein and Ely Porat 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.36 urn:nbn:de:0030-drops-259620 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2026.36 eng https://creativecommons.org/licenses/by/4.0/legalcode