Range Non-Overlapping Indexing

Google Tech Talks
July 31, 2007

ABSTRACT

We present a variation of the indexing problem involving constraints on the location of the pattern in the text. We call the variation \emph{range non-overlapping indexing} problem: given a text $T=t_{1}.. t_{n}$ over alphabet $\Sigma$, efficiently preprocess it such that future queries of the form ``given a pattern $P=p_{1}.. p_{m}$ over $\Sigma$ and two text locations $i \leq j$, find a sequence of locations where $P$ appears in $T$ between locations $i$ and $j$, such that the occurrences are \emph{non-overlapping} and their number is maximal''. This problem thus generalizes the \emph{string statistics problem}~\cite{AP96, BLOP02}, in which we only had...

Category:

Howto & Style

Tags:

• google
• howto
• range
• non
• overlapping
• indexing