An FM-index is a compressed text index supporting backward search through the Burrows-Wheeler transform and occurrence counts. Character rank queries locate a matching interval; sampled suffix array positions then allow the actual text positions to be recovered. Query length, number of matches and the chosen sampling density control different parts of the search cost.[ref]
Opportunistic Data Structures with Applications by Paolo Ferragina and others. §§3.1–3.2, counting and locating occurrences
New to topics? Read the docs here!