I recently implemented an FM-Index[1] which supports the following operations:
- count() the number of occurrences of a pattern P of length m in O(m) time.
- locate() determine the locations of all occurrences of a pattern P.
- extract() extract any substring from the Text
- recover the original text
The most interesting part is that the size constructed index depends on the compressibility of the text itself. For English text roughly half the size of the original text.
Construction time and memory requirements, however are not that great.