###
Text Indexing and Searching in Sublinear Time

####
J. Ian Munro, Gonzalo Navarro, and Yakov Nekrich

We introduce the first index that can be built in *o(n)* time for a text of
length *n*, and can also be queried in *o(q)* time for a pattern of
length *q*. On an alphabet of size *s*, our index uses
*O(n log s)* bits, is built in *O(n log s / sqrt(log n))*
deterministic time, and computes the number of occurrences of the
pattern in time *O(q / log_s n + log n log_s n)*. Each such occurrence
can then be found in *O(log n)* time.
Other trade-offs between the space usage and the cost of reporting occurrences
are also possible.