{
  "$type": "site.standard.document",
  "bskyPostRef": {
    "cid": "bafyreidnfytvapbjet7tuqy4nngfvkzp4jvhj2rmgbabfi5dah4jzgqvz4",
    "uri": "at://did:plc:3fychdutjjusoqeq24ljch6q/app.bsky.feed.post/3mkz5f3ymwzt2"
  },
  "coverImage": {
    "$type": "blob",
    "ref": {
      "$link": "bafkreiflo6xt7is6b2iafwghkjahlgggocme5jwjsbeuqqwcywuvjhmszm"
    },
    "mimeType": "image/png",
    "size": 24783
  },
  "path": "/abs/2605.00566v1",
  "publishedAt": "2026-05-04T00:00:00.000Z",
  "site": "https://arxiv.org",
  "tags": [
    "Moshe Lewenstein",
    "Ely Porat"
  ],
  "textContent": "**Authors:** Moshe Lewenstein, Ely Porat\n\nWe study the \"set parameterized matching\" problem, a generalization of the classical parameterized matching problem introduced by Baker. 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 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.",
  "title": "Set Parameterized Matching via Multi-Layer Hashing"
}