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\ldots n-1]$ be the BWT of $s[0\ldots 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=\texttt{nex}[i]$ to be the unique $j$ such that $b_j=a_i$. Then we know that $x_{j}=x_i+1$. Given $\texttt{nex}$, we can compute

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

We know that

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

Copy
#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>;