列表的最大后缀

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

我的解决方案是对问题最小旋转的解决方案进行一些修改。

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

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