The full text search idea is also called the FM Index: https://en.wikipedia.org/wiki/FM-index https://en.wikipedia.org/wiki/FM-index The BWT is one of those a

The full text search idea is also called the FM Index: https://en.wikipedia.org/wiki/FM-index https://en.wikipedia.org/wiki/FM-index The BWT is one of those almost magical tools for compression. But using it for speedy string search is a whole other amazing invention too.