In a sorted cyclic rotation matrix, the last-to-first mapping sends the th occurrence of a character in the last column to its th occurrence in the first column. For one-based rows, , where counts smaller characters and counts in the first 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.[ref]
Opportunistic Data Structures with Applications by Paolo Ferragina and others. §2, properties (a)–(b) and LF-mapping
Articles by others on the same topic
There are currently no matching articles.