Anzeige
Erschienen in:
2012 | OriginalPaper | Buchkapitel
Forbidden Patterns
verfasst von : Johannes Fischer, Travis Gagie, Tsvi Kopelowitz, Moshe Lewenstein, Veli Mäkinen, Leena Salmela, Niko Välimäki
Erschienen in: LATIN 2012: Theoretical Informatics
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
We consider the problem of indexing a collection of documents (a.k.a. strings) of total length n such that the following kind of queries are supported: given two patterns P + and P−, list all $\ensuremath{n_\text{match}}$ documents containing P + but notP−. This is a natural extension of the classic problem of document listing as considered by Muthukrishnan [SODA’02], where only the positive pattern P + is given. Our main solution is an index of size O(n3/2) bits that supports queries in $O(|\ensuremath{P^+}|+|\ensuremath{P^-}|+\ensuremath{n_\text{match}}+\sqrt{n})$ time.