Anzeige
Erschienen in:
2013 | OriginalPaper | Buchkapitel
Faster Range LCP Queries
verfasst von : Manish Patil, Rahul Shah, Sharma V. Thankachan
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
Range LCP (longest common prefix) is an extension of the classical LCP problem and is defined as follows: Preprocess a string
S
[1...
n
] so that
max
a
,
b
∈ {
i
...
j
}
LCP(
S
a
,
S
b
) can be computed efficiently for the input
i
,
j
∈ [1,
n
], where LCP(
S
a
,
S
b
) is the length of the longest common prefix of the suffixes of
S
starting at locations
a
and
b
. In this paper, we describe a linear space data structure with
O
((
j
−
i
)
1/2
log
ε
(
j
−
i
)) query time, where
ε
> 0 is any constant. This improves the linear space and
O
((
j
−
i
)loglog
n
) query time solution by Amir et. al. [ISAAC, 2011].