# Do Knuth-Morris-Pratt and Booth’s LCS algorithm work in linear time on lists of lists of integers?

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?

• Is it possible that two strings are compared in constant expected time? That would be the case, for example, if they are "different" enough on average so the typical case is that you only need to look at a few characters to decide. Jul 25 at 13:35
• @Steven, that’s an interesting remark, but I am not currently aware of any such patterns in our data. (I mean, we are not comparing arbitrary strings, but I’d rather not go into details unless it’s really necessary in order to answer the question, since they’re rather complicated.) Jul 25 at 13:39
• @Steven, I’ve tried a little test and it seems like it works in linear time even when all strings are identical, which triggers the worst case for the comparisons (while not making a difference for Booth’s algorithm itself, unless I’m mistaken). Jul 25 at 14:01
• If your data distribution allows O(1) hash tables, you can precompute a hash table from strings to small integers in time linear to the total size of the strings, and then apply a linear time algorithm on the list of small integers. You'd probably lose all the benefits of algorithms that are fast because they manage to completely skip a lot of elements, though, so it fits the letter but not the spirit of the question (hence why I'm not posting this as an answer). But maybe you can get the benefits of both worlds with some kind of laziness or caching? Jul 29 at 18:01
• @Gilles'SO-stopbeingevil', your remark (while interesting, and thank you for it) made me realise that I should probably avoid the term “strings” here, since we’re actually dealing with lists of integers bounded by the number of elements $n$ in the list. I’m modifying the questions accordingly. Jul 29 at 18:36