这个问题试图找到给定列表的字典序最大后缀。
假设我们有一个数组/列表 [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(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]
在字典序上比它大。
关于algorithm - 列表的最大后缀,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/21409561/