@article{2001297,
author={Raphaël Clifford and Benjamin Sach},
title={Permuted Function Matching},
journal={Information Processing Letters},
volume={110},
number={22},
pages={1012--1015},
month={October},
year={2010},
abstract={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.},
abstract-url={http://www.cs.bris.ac.uk/Publications/pub_master.jsp?id=2001297},
url={http://www.cs.bris.ac.uk/Publications/Papers/2001297.pdf},
keyword={Algorithms,Pattern Matching},
pubtype={101}
}