IMHO, the FM-index deserves to be highlighted. That it is possible to store a string in a compressed format which can answer length-P substring queries in O(P)

IMHO, the FM-index deserves to be highlighted. That it is possible to store a string in a compressed format which can answer length-P substring queries in O(P) time (with good constant factors) is quite surprising at first sight. I recently wrote a few words about this here: http://ocfnash.wordpress.com/2014/01/03/dna-of-a-password-disaster/ http://ocfnash.wordpress.com/2014/01/03/dna-of-a-password-di... By the time I finished I decided the whole area was exciting and seems not at all as well known as it should be. I also think there are plenty of related, as-yet-undiscovered ideas, waiting for somebody to find them!