algorithm - 列表的最大后缀

Question

这个问题试图找到给定列表的字典序最大后缀。

---

假设我们有一个数组/列表 [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列表中找到字典序最大的一个。

---

例如[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)，并且不应使用后缀树(也没有后缀数组)。

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

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

我的解决方案是对问题Minimum Rotations的解决方案稍作修改.

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

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