As a subroutine for an algorithm we’re working on, we need to compute the lexicographically minimal rotation (or least circular shift) of a list of lists of integers.
The problem, in the more usual setting of strings of (atomic) symbols, is well-known and several linear time algorithms have been published, the first one being Booth’s LCS algorithm, which is based on Knuth-Morris-Pratt.
However, the analyses proving the $O(n)$ runtime that I find in the literature all seem to be based on the finite alphabet assumption or, to be more precise, on constant-time comparisons between symbols.
As mentioned above, in our application we have lists $\langle \ell_1, \ldots, \ell_m \rangle$ of $m$ lists of integers, where each list $\ell_i$ contains integers whose value is bounded by the total length $n = |\ell_1| + \cdots + |\ell_m|$, rather than a string of atomic symbols, so comparing two lists $\ell_i$, $\ell_j$ by lexicographic order requires time proportional to length of the longest common prefix of $\ell_i$ and $\ell_j$ (here, we assume that a comparison between two integers can be carried out in constant time).
Experimentally, on our data (which is admittedly not arbitrary lists of lists), it seems that Booth’s LCS algorithm does indeed work in time $O(n)$ in this case, i.e., in linear time with respect of the sum of the length of the lists.
Is there a simple argument I’m missing (or a complicated argument published somewhere) that proves that this is indeed the case, either for Booth’s LCS algorithm, or alternatively for Knuth-Morris-Pratt? Or is this actually false?