列表的最大后缀

该问题试图找到给定列表的词典最大后缀。

假设我们有一个数组/列表 [e1;e2;e3;e4;e5]。

那么 [e1;e2;e3;e4;e5] 的所有后缀为：

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

那么我们的目标就是找到上面的字典序最大的一个5 lists.

例如，[1;2;3;1;0] 的所有后缀都是

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

字典顺序最大后缀是[3;1;0]从上面的例子来看。

最简单的算法就是将所有后缀一一比较，并始终记录最大值。时间复杂度为O(n^2)因为比较两个列表需要O(n).

然而，期望的时间复杂度是O(n) 并且没有后缀树（也没有后缀数组）应该使用。

请注意，列表中的元素可能并不不同

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;
}

我的解决方案是对问题的解决方案稍作修改最小旋转次数 http://www.spoj.com/problems/MINMOVE/.

在上面的代码中，每次进入循环时，都会保留i < j， 和所有a[p...n] (0<=p<j && p!=i)不是最大后缀。然后为了决定哪一个a[i...n] and a[j...n]字典顺序较少，使用 for 循环查找最少的k使a[i+k]!=a[j+k]，然后更新i and j根据k.

我们可以跳过k元素为i or j，并且仍然保持真实，所有a[p...n] (0<=p<j && p!=i)不是最大后缀。例如，如果a[i+k]<a[j+k], then a[i+p...n](0<=p<=k)不是最大后缀，因为a[j+p...n]按字典顺序比它大。