FM-index

Here you will find an easy-to-understand explanation of an interesting data structure: FM-index.

Table of contents:

1. Intro. Suffix array.

2. Burrows-Wheeler matrix.

3. Ranking characters.

4. Index!

5. Optimal search.

Extended index

Row	F	L	rank $	rank a	rank c	rank o	SA
0	$1	a1	0	1	0	0	5
1	a1	o1	0	1	0	1	4
2	c1	o2	0	1	0	2	2
3	c2	$1	1	1	0	2	0
4	o1	c1	1	1	1	2	3
5	o2	c2	1	1	2	2	1
6			1	1	2	2	1