The classic string indexing problem is to preprocess a string S into a compact data structure that supports efficient subsequent pattern matching queries, that is, given a pattern string P, report all occurrences of P within S. In this paper, we study a basic and natural extension of string indexing called the string indexing for top-k close consecutive occurrences problem (SITCCO). Here, a consecutive occurrence is a pair (i,j), i < j, such that P occurs at positions i and j in S and there is no occurrence of P between i and j, and their distance is defined as j-i. Given a pattern P and a parameter k, the goal is to report the top-k consecutive occurrences of P in S of minimal distance. The challenge is to compactly represent S while supporting queries in time close to length of P and k. We give two new time-space trade-offs for the problem.   Our first result achieves near-linear space and optimal query time  , and our second result achieves linear space and near optimal query time . Along the way, we develop several techniques of independent interest, including a new translation of the problem into a line segment intersection problem and a new recursive clustering technique for trees.
The classic string indexing problem is to preprocess a string S into a compact data structure that supports efficient subsequent pattern matching queries, that is, given a pattern string P, report all occurrences of P within S. In this paper, we study a basic and natural extension of string indexing called the string indexing for top-k close consecutive occurrences problem (SITCCO). Here, a consecutive occurrence is a pair (i,j), i < j, such that P occurs at positions i and j in S and there is no occurrence of P between i and j, and their distance is defined as j-i. Given a pattern P and a parameter k, the goal is to report the top-k consecutive occurrences of P in S of minimal distance. The challenge is to compactly represent S while supporting queries in time close to length of P and k. We give two time-space trade-offs for the problem. Let n be the length of S, m the length of P, and \epsilon\in(0,1 . Our first result achieves O(n\log n) space and optimal query time of O(m+k) , and our second result achieves linear space and query time O(m+k^{1+\epsilon . Along the way, we develop several techniques of independent interest, including a new translation of the problem into a line segment intersection problem and a new recursive clustering technique for trees.
D
new
A
Let n be the length of S, m the length of P, and \epsilon\in(0,1
A
.
R
near-linear
O(n\log n)
A
of O(m+k)
R
near optimal query time
query time O(m+k^{1+\epsilon