1 Rotation Matrix (Sorted)
All cyclic rotations of the input string (+ $), sorted lexicographically. First column (F) | Last column (L) = BWT
Enter a string and click "Build"
2 BWT Result & Suffix Array
The last column forms the BWT string. Suffix Array gives original positions.
Build the transform first
3 FM-Index Tables
Build the index first
4 Backward Search
FM-Index enables O(m) pattern matching by searching backwards through the pattern.
How Backward Search Works:
Starting from the last character of the pattern, we maintain a range [sp, ep] in the suffix array. For each character c, we update:
When sp ≤ ep, matches exist at positions SA[sp..ep].
Starting from the last character of the pattern, we maintain a range [sp, ep] in the suffix array. For each character c, we update:
sp = C[c] + Occ(c, sp-1) and ep = C[c] + Occ(c, ep) - 1When sp ≤ ep, matches exist at positions SA[sp..ep].