CSES - String Transform

GFG does an okay (?) job of explaining it and giving some intuition. But the code can be so much shorter ...

My Implementation

Let $t[0\dots n-1]$ be the BWT of $s[0\dots n-1]$, where $s$ ends with a character that is smaller than all other characters in $s$ (# in this case).

Consider all indices modulo $n$. If $t_i$ corresponds to $s_{x_i-1}$ (the last character of the $i$-th smallest rotation) then define

$a_i$ corresponds to the $i$_th smallest rotation of $s$, and $b_i$ is formed by cyclically shifting $a_i$ by one character. $t_i$ is the last character of $a_i$ and the first character of $b_i$.

Define $j=\text{nex}[i]$ to be the unique $j$ such that $b_j=a_i$. Then we know that $x_j=x_i+1$. Given $\text{nex}$, we can compute

so $s_i=s_{{\text{nex}}^{i+1}[0]}=t_{{\text{nex}}^{i+2}[0]}$ for all $i$.

We know that

so we can sort the $b_i$ using a stable sort. Then $\text{nex}[i]$ is just the index of the $i$-th rotation in this sort!

1#include <bits/stdc++.h>
2using namespace std;
3 
4using ll = long long;
5using ld = long double;
6using db = double; 
7using str = string; // yay python!
8
9using pi = pair<int,int>;
10using pl = pair<ll,ll>;