摘要：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 Ïf, our index uses O(n log Ïf) bits, is built in O(n log Ïf / â^S{log n}) deterministic time, and computes the number of occurrences of the pattern in time O(q/log_Ïf n + log n log_Ïf 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.
