Max suffix of a list

algorithm

Solution

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.

Problem

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

Original source