Max suffix of a list

Question

This problem is trying to find the lexicographical max suffix of a given list.

---

Suppose we have an array/list [e1;e2;e3;e4;e5].

Then all suffixes of [e1;e2;e3;e4;e5] are:

[e1;e2;e3;e4;e5]
[e2;e3;e4;e5]
[e3;e4;e5]
[e4;e5]
[e5]

Then our goal is to find the lexicographical max one among the above 5 lists.

---

for example, all suffixes of [1;2;3;1;0] are

[1;2;3;1;0]
[2;3;1;0]
[3;1;0]
[1;0]
[0].

The lexicographical max suffix is [3;1;0] from above example.

---

The straightforward algorithm is just to compare all suffixes one by one and always record the max. The time complexity is O(n^2) as comparing two lists need O(n).

However, the desired time complexity is O(n) and no suffix tree (no suffix array either) should be used.

please note that elements in the list may not be distinct

Answer 1

int max_suffix(const vector<int> &a) 
{
  int n = a.size(), 
      i = 0, 
      j = 1, 
      k;

  while (j < n) 
  {
    for (k = 0; j + k < n && a[i + k] == a[j + k]; ++k);

    if (j + k == n) break;

    (a[i + k] < a[j + k] ? i : j) += k + 1;

    if (i == j) 
        ++j;
    else if (i > j) 
         swap(i, j);
  }
  return i;
}

My solution is a little modification of the solution to the problem Minimum Rotations.

In the above code, each time it step into the loop, it's keeped that i < j, and all a[p...n] (0<=p<j && p!=i) are not the max suffix. Then in order to decide which of a[i...n] and a[j...n] is less lexicographical, use the for-loop to find the least k that make a[i+k]!=a[j+k], then update i and j according to k.

We can skip k elements for i or j, and still keep it true that all a[p...n] (0<=p<j && p!=i) are not the max suffix. For example, if a[i+k]<a[j+k], then a[i+p...n](0<=p<=k) is not max suffix, since a[j+p...n] is lexicographically greater than it.