Anzeige
Erschienen in:
2010 | OriginalPaper | Buchkapitel
Parameterized Searching with Mismatches for Run-Length Encoded Strings
(Extended Abstract)
verfasst von : Alberto Apostolico, Péter L. Erdős, Alpár Jüttner
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
Two strings
y
and
y′
of equal length over respective alphabets Σ
y
and Σ
y
′
are said to
parameterized match
if there exists a bijection
π
: Σ
y
→Σ
y
′
such that
π
(
y
) =
y′
, i.e., renaming each character of
y
according to its corresponding element under
π
yields
y′
. (Here we assume that all symbols of both alphabets are used somewhere.) Two natural problems are then
parameterized matching
, which consists of finding all positions of some text
x
where a pattern
y
parameterized matches a substring of
x
, and
approximate parameterized matching
, which seeks, at each location of
x
, a bijection
π
maximizing the number of parameterized matches at that location.