Generalised matching
Raphaël Clifford, Benjamin Sach, Generalised matching. String Processing and Information Retrieval, 16th International Symposium, SPIRE 2009. ISBN 978-3-642-03783-2, pp. 295–301. August 2009. PDF, 151 Kbytes.Abstract
Given a pattern p over an alphabet Σ_p and a text t over an alphabet Σ_t , we consider the problem of determining a mapping f from Σ_p to Σ_t^+ such that t = f(p_1)f(p_2)...f(p_m). This class of problems, which was first introduced by Amir and Nor in 2004, is defined by different constraints on the mapping f. We give NP-Completeness results for a wide range of conditions. These include when f is either many-to-one or one-to-one, when Σ_t is binary and when the range of f is limited to strings of constant length. We then introduce a related problem we term pattern matching with string classes which we show to be solvable efficiently. Finally, we discuss an optimisation variant of generalised matching and give a polynomial-time min(1,\sqrt{k/OPT})-approximation algorithm for fixed k.