Function Matching
Amihood Amir, Yonatan Aumann, Moshe Lewenstein, Ely Porat · SIAM Journal on Computing · 2006
We present problems in the following three application areas: identifying similar codes in which global register reallocation and spill code minimization were done (programming languages); protein threading (computational biology); and searching for color icons under different color maps (image processing). We introduce a new search model called function matching that enables us to solve the above problems. The function matching problem has as its input a text T of length n over alphabet $\Sigma_T$ and a pattern $P = P[1] P[2] \cdots P[m]$ of length m over alphabet $\Sigma_P$. We seek all text locations i, where the m-length substring that starts at i is equal to $f(P[1]) f(P[2]) \cdots f(P[m])$, for some function $f: \Sigma_P \rightarrow \Sigma_T$. We give a randomized algorithm that solves the function matching problem in time $O(n\log n)$ with probability ${1\over n}$ of declaring a false positive. We give a deterministic algorithm whose time is $O(n |\Sigma_P| \log m)$ and show that it is optimal in the convolutions model. We use function matching to efficiently solve the problem of two-dimensional parameterized matching.