FM-Index Backward Search

The FM-Index is a compressed full-text substring index based on the Burrows-Wheeler Transform (BWT). It allows for fast pattern matching by simulating backward search, finding the count and location of a pattern in the original text without explicitly storing the entire suffix array or the text itself.

Experiment

You can interact with the FM-Index using the provided controls. Try the following steps to observe the backward search process:

1. Open the FM-Index Backward Search module.
2. Set Text to "Mississippi".
3. Set Pattern to "issi".
4. Set Rank character to "s" and Rank prefix to "6".
5. Observe the search trace and the highlighted interval on the BWT. The actual search interval updates backward character by character.
6. Notice how setting Pattern to "Empty" selects the entire text interval, while setting it to "zzz" results in an empty interval [0, 0) since the characters do not exist.