Anzeige
Erschienen in:
2014 | OriginalPaper | Buchkapitel
Shortest Unique Queries on Strings
verfasst von : Xiaocheng Hu, Jian Pei, Yufei Tao
Erschienen in: String Processing and Information Retrieval
Verlag: Springer International Publishing
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
Let
D
be a long input string of
n
characters (from an alphabet of size up to 2
w
, where
w
is the number of bits in a machine word). Given a substring
q
of
D
, a
shortest unique query
returns a shortest unique substring of
D
that contains
q
. We present an optimal structure that consumes
O
(
n
) space, can be built in
O
(
n
) time, and answers a query in
O
(1) time. We also extend our techniques to solve several variants of the problem optimally.