这个问题是试图找到一个给定列表的辞书最多的后缀。
假设我们有一个数组/列表[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(常量矢量< INT>&安培;一)
{
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]<一[J + K]我:?j)条+ = K + 1;
如果(我== j)条
+ D];
否则,如果(I> j)条
交换(I,J);
}
返回我;
}
我的解决方案是解决问题的办法最低轮作一点修改。
在上面的code,每次都步入循环,它的keeped了 I< Ĵ
,以及所有 A [P ... N](0℃= P< J&安培;&安培;!P = I)
不最大后缀。然后,以决定哪些 A [1 ... N]
和 A [J ... N]
较少辞书,使用for循环,找到至少 K
,使 A [1 + K]!=一[J + K]
,然后更新我
和Ĵ
按 K
。
我们可以跳过 K
为元素我
或Ĵ
,仍然保持其真实,所有的 A [P ... N](0℃= P< J&安培;&安培;!P = I)
不是最大后缀。例如,如果 A [1 + K]<一[J + K]
,然后 A [1 +π... N]( 0℃= P< = 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.