Skip to main content

Generalised matching

Rapha?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.


Given a pattern p over an alphabet I#_p and a text t over an alphabet I#_t , we consider the problem of determining a mapping f from I#_p to I#_t^+ such that ta??= 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 I#_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.

Bibtex entry.

Publication Admin