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.