Range Non-Overlapping Indexing

Channel:

Google TechTalks

Subscribers:

348,000

Published on October 9, 2007 2:01:41 AM ● Video Link: https://www.youtube.com/watch?v=E05CEubQ4tw

Duration: 32:43

500 views

1

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...