<p>This doesn't answer your question about why your naive comparisons are fast, but the following appears to allow comparisons in constant time:</p>
<ul>
<li>Concatenate the lists of integers together</li>
<li>Compute the suffix tree of the result, which can be done in linear time after sorting the integers that appear in it (possible in linear time from your assumption that the integers have magnitude bounded by the input length)</li>
<li>For each list of integers, find where you get to in the suffix tree by following a matching path down from the root</li>
<li>Replace each list of integers in your list of lists by the index of the resulting suffix tree node, as numbered using a preorder traversal of the suffix tree</li>
<li>Compare sequences by these numbers, with ties broken by length</li>
</ul>

CC BY-SA 4.0
2022-08-11T13:15:06.143Z
Thanks, I think we have already found (what I believe to be) a simpler alternative linear-time solution for our specific case, but this does indeed seem to be another possibility. (I’m not accepting this answer not because it’s not insightful, it is!, but because I’m really interested in the efficiency of the naive approach.)
Antonio E. Porreca
CC BY-SA 4.0
2022-08-10T19:31:11.350Z
2022-08-10T19:31:11.350Z
David Eppstein
<p>As a subroutine for an algorithm we’re working on, we need to compute the <a href="https://en.wikipedia.org/wiki/Lexicographically_minimal_string_rotation" rel="nofollow noreferrer">lexicographically minimal rotation</a> (or least circular shift) of <em>a list of lists of integers</em>.</p>
<p>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 <a href="https://www.cs.ubc.ca/%7Eksbooth/PUB/LCS.shtml" rel="nofollow noreferrer">Booth’s LCS algorithm</a>, which is based on <a href="https://en.wikipedia.org/wiki/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm" rel="nofollow noreferrer">Knuth-Morris-Pratt</a>.</p>
<p>However, the analyses proving the <span class="math-container">$O(n)$</span> 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.</p>
<p>As mentioned above, in our application we have lists <span class="math-container">$\langle \ell_1, \ldots, \ell_m \rangle$</span> of <span class="math-container">$m$</span> lists of  integers, where each list <span class="math-container">$\ell_i$</span> contains integers whose value is bounded by the total length <span class="math-container">$n = |\ell_1| + \cdots + |\ell_m|$</span>, rather than a string of atomic symbols, so comparing two lists <span class="math-container">$\ell_i$</span>, <span class="math-container">$\ell_j$</span> by lexicographic order requires time proportional to length of the longest common prefix of <span class="math-container">$\ell_i$</span> and <span class="math-container">$\ell_j$</span> (here, we assume that a comparison <em>between two integers</em> can be carried out in constant time).</p>
<p>Experimentally, on our data (which is admittedly not arbitrary lists of lists), it seems that Booth’s LCS algorithm does indeed work in time <span class="math-container">$O(n)$</span> in this case, i.e., in linear time with respect of the sum of the length of the lists.</p>
<p>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?</p>

CC BY-SA 4.0
2022-07-25T13:35:10.413Z
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.
Steven
CC BY-SA 4.0
2022-07-25T13:39:02.563Z
@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.)
Antonio E. Porreca
CC BY-SA 4.0
2022-07-25T14:01:26.493Z
@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).
Antonio E. Porreca
CC BY-SA 4.0
2022-07-29T18:01:03.593Z
If your data distribution allows [O(1) hash tables](https://cs.stackexchange.com/q/477), 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?
Gilles 'SO- stop being evil'
CC BY-SA 4.0
2022-07-29T18:36:09.207Z
@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.
Antonio E. Porreca
CC BY-SA 4.0
2022-07-31T19:53:03.420Z
How doe list compare when they don't have the same length? What do we know about the integers? are they integers representable in $O(\log n)$ bits? or there are abstract objects where only comparison can be applied on them?
Chao Xu
CC BY-SA 4.0
2022-07-31T20:02:59.303Z
@ChaoXu, the lists are compared according to the lexicographic order induced by the order on the integers, so length only matters if one is a prefix of the other (in that case, the shorter one is inferior). As for the integers, I’m considering a RAM model where they can be compared in O(1) time, and comparison is indeed the only operation applied by KMP and Booth (or rather, by the list-of-ints lexicographic comparison algorithm).
Antonio E. Porreca
CC BY-SA 4.0
2022-07-31T20:11:04.660Z
If all values are equal, then it would be linear. Since each comparison takes $n/m$ time and $O(m)$ comparisons will be made, so $O(n)$ time in total.
Chao Xu
CC BY-SA 4.0
2022-08-01T15:41:16.427Z
@ChaoXu yes, that much is clear to me.
Antonio E. Porreca
<ds.algorithms><string-matching>
Do Knuth-Morris-Pratt and Booth’s LCS algorithm work in linear time on lists of lists of integers?
Antonio E. Porreca
# Do Knuth-Morris-Pratt and Booth’s LCS algorithm work in linear time on lists of lists of integers?

(Asked by: username_0 on 2022-07-25)

As a subroutine for an algorithm we’re working on, we need to compute the [lexicographically minimal rotation](https://en.wikipedia.org/wiki/Lexicographically_minimal_string_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](https://www.cs.ubc.ca/%7Eksbooth/PUB/LCS.shtml), which is based on [Knuth-Morris-Pratt](https://en.wikipedia.org/wiki/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm).

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?

**Tags:** ds.algorithms, string-matching

> **Comments:**
> **username_1**: 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.  
> **username_0**: @username_1, 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.)  
> **username_0**: @username_1, 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).  
> **username_2**: If your data distribution allows [O(1) hash tables](https://cs.stackexchange.com/q/477), 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?  
> **username_0**: @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.  
> **username_3**: How doe list compare when they don't have the same length? What do we know about the integers? are they integers representable in $O(\log n)$ bits? or there are abstract objects where only comparison can be applied on them?  
> **username_0**: @ChaoXu, the lists are compared according to the lexicographic order induced by the order on the integers, so length only matters if one is a prefix of the other (in that case, the shorter one is inferior). As for the integers, I’m considering a RAM model where they can be compared in O(1) time, and comparison is indeed the only operation applied by KMP and Booth (or rather, by the list-of-ints lexicographic comparison algorithm).  
> **username_3**: If all values are equal, then it would be linear. Since each comparison takes $n/m$ time and $O(m)$ comparisons will be made, so $O(n)$ time in total.  
> **username_0**: @ChaoXu yes, that much is clear to me.  

---

## 1 answers

### Answer by username_4 on 2022-08-10. Score: 5

This doesn't answer your question about why your naive comparisons are fast, but the following appears to allow comparisons in constant time:

* Concatenate the lists of integers together
* Compute the suffix tree of the result, which can be done in linear time after sorting the integers that appear in it (possible in linear time from your assumption that the integers have magnitude bounded by the input length)
* For each list of integers, find where you get to in the suffix tree by following a matching path down from the root
* Replace each list of integers in your list of lists by the index of the resulting suffix tree node, as numbered using a preorder traversal of the suffix tree
* Compare sequences by these numbers, with ties broken by length

> **Comments:**
> **username_0**: Thanks, I think we have already found (what I believe to be) a simpler alternative linear-time solution for our specific case, but this does indeed seem to be another possibility. (I’m not accepting this answer not because it’s not insightful, it is!, but because I’m really interested in the efficiency of the naive approach.)  

---

