| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 427464 | Information Processing Letters | 2010 | 4 Pages |
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 ΣpΣp to ΣtΣt with the property that f(pj)=ti+j−1f(pj)=ti+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(nlog|Σp|)O(nlog|Σp|) time. We then give a 1/2-approximation for a Hamming distance based optimisation variant by reduction to multiple knapsack with colour constraints.
Research highlights► The combination of function matching and permuted matching is shown to be NP-Complete. ► The combination of parameterised matching and permuted matching is shown to be in P. ► A 1/2-approximation for an optimisation variant of permuted function matching is given.
