Anzeige
Erschienen in:
2009 | OriginalPaper | Buchkapitel
Generalised Matching
verfasst von : Raphael Clifford, Aram W. Harrow, Alexandru Popa, Benjamin Sach
Erschienen in: String Processing and Information Retrieval
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
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
${\Sigma}_{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
.