GFG does an okay (?) job of explaining it and giving some intuition. But the code can be so much shorter ...
Let be the BWT of , where ends with a
character that is smaller than all other characters in (#
in this case).
Consider all indices modulo . If corresponds to (the last character of the -th smallest rotation) then define
corresponds to the _th smallest rotation of , and is formed by cyclically shifting by one character. is the last character of and the first character of .
Define to be the unique such that . Then we know that . Given , we can compute
so for all .
We know that
so we can sort the using a stable sort. Then is just the index of the -th rotation in this sort!
#include <bits/stdc++.h>using namespace std;using ll = long long;using ld = long double;using db = double;using str = string; // yay python!using pi = pair<int, int>;using pl = pair<ll, ll>;