Skip to main content

Permuted Function Matching

Rapha?Permuted Function Matching. Information Processing Letters, 110(22), pp. 1012–1015. October 2010. PDF, 130 Kbytes.


We consider the combination of function and permuted matching, each of which has fast solutions in their own right. Given a pattern p of length m and a text t of length n, a function match at position i of the text is a mapping f from Sigma_p to Sigma_t with the property that f(p_j) = t_(i+j-1) for all j. We show that the problem of determining for each substring of the text, if any permutation of the pattern has a function match is in general NP-Complete. However where the mapping is also injective, so called parameterised matching, the problem can be solved efficiently in O(n log |Sigma_p|) time. We then give a 1/2-approximation for a Hamming distance based optimisation variant by reduction to multiple knapsack with colour constraints.

Bibtex entry.

Publication Admin