Anzeige
Erschienen in:
2007 | OriginalPaper | Buchkapitel
Finding Witnesses by Peeling
verfasst von : Yonatan Aumann, Moshe Lewenstein, Noa Lewenstein, Dekel Tsur
Erschienen in: Combinatorial Pattern Matching
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
In the
k
-matches problem, we are given a pattern and a text, and for each text location the goal is to list all, but not more than
k
, matches between the pattern and the text. This problem is one of several string matching problems that ask to not only to find where the pattern matches the text, under different “match” definitions, but also to provide
witnesses
to the match. Other such problems include:
k
-aligned ones [4],
k
-witnesses, and
k
-mismatches [18]. In addition, the solution to several other string matching problems relies on the efficient solution of the witness finding problems.
In this paper we provide a general efficient method for solving such witness finding problems. We do so by casting the problem as a generalization of group testing, which we then solve by a process which we call
peeling
. Using this general framework we obtain improved results for all of the above problems. We also show that our method also solves a couple of problems outside the pattern matching domain.