论文库

原文摘要

Two strings are considered to have parameterized matching when there exists a bijection of the parameterized alphabet onto itself such that it transforms one string to another. Parameterized matching has application in software duplication detection, image processing, and computational biology. We consider the problem for which a pattern $p$, a text $t$ and a mismatch tolerance limit $k$ are given and the goal is to find all positions in text $t$ for which pattern $p$ parameterized matches with $|p|$-length substrings of $t$ with at most $k$ mismatches. The number of mismatches is the Hamming distance under the best bijection, which we call the parameterized distance. Our main result is an algorithm that computes the parameterized distance at every position of the text, and hence solves this problem for every $k$ at once. Its running time is $O((σ_p^2+σ_s)\, n\log m + n\,T_M)$, where $n = |t|$, $m=|p|$, $σ_p$ and $σ_s$ are the numbers of parameterized and static characters, and $T_M$ is the time to compute one maximum weight matching in a bipartite graph with $2σ_p$ vertices. With the algorithm of Gabow and Tarjan, $T_M=O(σ_p^{2.5}\log(σ_p m))$. Since this bound does not depend on $k$, our algorithm improves the algorithm by Hazay, Lewenstein and Sokol for $k=\tildeΩ(σ_p^{5/3}+σ_s^{2/3})$.