String-searching algorithm

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]

Backward search finds a query's matching interval in a suffix array by processing the query from right to left. With inclusive one-based interval $[l,r]$, prepending $c$ changes it to $[C(c)+\mathrm{Occ}(c,l-1)+1,C(c)+\mathrm{Occ}(c,r)]$. An empty interval means no match. This works through the occurrence-order property of the last-to-first mapping.^[ref]

In a sorted cyclic rotation matrix, the last-to-first mapping sends the $k$th occurrence of a character in the last column to its $k$th occurrence in the first column. For one-based rows, $\mathrm{LF}(r)=C(L_r)+\mathrm{Occ}(L_r,r)$, where $C(c)$ counts smaller characters and $\mathrm{Occ}(c,r)$ counts $c$ in the first $r$ entries of the last column. It moves a rotation's start one character backwards cyclically. Equal characters retain the lexicographic order of their following sequences, which proves the occurrence-order rule.^[ref]

The Burrows-Wheeler transform appends a unique smallest terminator to a string, sorts its cyclic rotations in lexicographic order, and records the last column. It is reversible because the first and last columns contain the same characters and the last-to-first mapping preserves the occurrence order of each character. The resulting letter arrangement supports both compression and backward search.^[ref]

A transition to a shorter suffix match after an attempted extension fails. In a Knuth-Morris-Pratt automaton, the prefix function determines the next shorter matching prefix.

For a string $s$, the value ${\pi }_i$ is the length of the longest proper prefix of $s_0\cdots s_i$ that is also its suffix. Repeatedly following these lengths lists all proper borders of a string; this is the failure-link information used by the Knuth-Morris-Pratt algorithm.