Optimal-Time Move Structure Construction

Abstract

The move structure represents a permutation $\ddot{I}€$ of $[0,n)$ by partitioning the domain into $O(r)$ disjoint, contiguously permuted intervals, with $r$ being the minimum number of such intervals. This data structure occupies $O(r)$ words of space and enables $O(1)$-time computation of $\ddot{I}€(i)$ given the interval that contains $i$. For permutations where $r\ll n$, this provides an efficient, compressed representation for navigation. While existing best $O(r)$-space construction approaches require $O(r\log r)$-time, we present an optimal $O(r)$-time and space construction algorithm. This is achieved by replacing balanced search trees with pointer-based lists by introducing a bidirectional strategy that synchronizes construction of the structures for $\ddot{I}€$ and its inverse $\ddot{I}{€}^{-1}$ in a single, unified pass. By applying this algorithm, we achieve the first optimal $O(n)$-time construction of the longest common prefix (LCP) array from a run-length-encoded Burrows-Wheeler transform (RLBWT) of $r$ runs in $O(r)$ working space. Empirical evaluation on pangenome-scale data confirms that our move structure construction algorithm is consistently faster than the previous best, achieving speedups of up to $\sim 2\times$ with comparable memory usage.