列表中的最大后缀 [英] Max suffix of a list

问题描述

这个问题是试图找到一个给定列表的辞书最多的后缀。

---

假设我们有一个数组/列表[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）和无后缀树（没有后缀数组要么）应该被使用。

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

解决方案

  INT max_suffix（常量矢量＆lt; INT＆GT;＆安培;一）
{
  INT N = a.size（）
      I = 0，
      J = 1，
      K表;

  而（J＆n种）
  {
    为（K = 0; J + K＆n种安培;＆安培;一个[I + K] ==一个[J + K] ++ K）;

    如果（j + K = = n）的突破;

    （A [1 + K]＆LT;一[J + K]我：？j）条+ = K + 1;

    如果（我== j）条
        + D];
    否则，如果（I＆GT; j）条
         交换（I，J）;
  }
  返回我;
}
 

我的解决方案是解决问题的办法最低轮作一点修改。

在上面的code，每次都步入循环，它的keeped了 I＆LT; Ĵ，以及所有 A [P ... N]（0℃= P＆LT; J＆安培;＆安培;！P = I）不最大后缀。然后，以决定哪些 A [1 ... N] 和 A [J ... N] 较少辞书，使用for循环，找到至少 K ，使 A [1 + K]！=一[J + K] ，然后更新我和Ĵ按 K 。

我们可以跳过 K 为元素我或Ĵ，仍然保持其真实，所有的 A [P ... N]（0℃= P＆LT; J＆安培;＆安培;！P = I）不是最大后缀。例如，如果 A [1 + K]＆LT;一[J + K] ，然后 A [1 +π... N]（ 0℃= P＆LT; = K）不是最大的后缀，因为 A [J + P ... N] 是字典序大于它。

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

解决方案

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.

这篇关于列表中的最大后缀的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！