= Last-to-first mapping
{title2=$\operatorname{LF}(r)=C(L_r)+\operatorname{Occ}(L_r,r)$}
In a sorted <cyclic rotation> matrix, the <last-to-first mapping> sends the $k$th occurrence of a character in the last column to its $k$th occurrence in the first column. For one-based rows, $\operatorname{LF}(r)=C(L_r)+\operatorname{Occ}(L_r,r)$, where $C(c)$ counts smaller characters and $\operatorname{Occ}(c,r)$ counts $c$ in the first $r$ entries of the last column. It moves a rotation's start one character backwards cyclically. Equal characters retain the <lexicographic order> of their following sequences, which proves the occurrence-order rule.<Opportunistic Data Structures with Applications by Paolo Ferragina and others>[§2, properties (a)–(b) and LF-mapping]{ref}
Back to article page
