Generalised matching

Raphaël Clifford, Harrow AW, Popa A, Benjamin Sach

Research output: Contribution to journalArticle (Academic Journal)

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.
Translated title of the contributionGeneralised matching
Original languageEnglish
Pages (from-to)295-301
JournalString Processing and Information Retrieval, 16th International Symposium, SPIRE 2009
Publication statusPublished - 2009

Bibliographical note

ISBN: 9783642037832
Publisher: Springer
Name and Venue of Conference: String Processing and Information Retrieval, 16th International Symposium, SPIRE 2009
Other identifier: 2001173

Fingerprint Dive into the research topics of 'Generalised matching'. Together they form a unique fingerprint.

Cite this