Set Parameterized Matching via Multi-Layer Hashing
This work provides an efficient solution for a generalization of parameterized matching, which is relevant for applications in bioinformatics and text processing where positions contain sets of characters.
The paper introduces a randomized algorithm for set parameterized matching, achieving O(N+M) time with high probability, where N is text size and M is pattern size. The algorithm uses a novel three-layer hashing scheme based on Karp-Rabin fingerprinting.
We 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.