Generalised matching

Raphael Clifford, Aram W. Harrow, Alexandru Popa, Benjamin Sach

Research output: Chapter in Book/Report/Conference proceedingConference contribution

15 Citations (Scopus)


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(p2)...f(pm). 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, √k/OPT)-approximation algorithm for fixed k.

Original languageEnglish
Title of host publicationString Processing and Information Retrieval - 16th International Symposium, SPIRE 2009, Proceedings
Number of pages7
Publication statusPublished - Nov 9 2009
Event16th International Symposium on String Processing and Information Retrieval, SPIRE 2009 - Saariselka, Finland
Duration: Aug 25 2009Aug 27 2009

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume5721 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Other16th International Symposium on String Processing and Information Retrieval, SPIRE 2009

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

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

Cite this