删除 K 个第一个、第二个、最后一个或倒数第二个字符后的最小字典序字符串
Minimum Lexicographical String after K removals of first, second, last or penultimate characters
问题：
给定一个字符串SS.length() <= 5.10^5和一个整数KK <= S.length()。对于每次删除，您可以：
- 删除字符串的第一个字符
- 删除字符串的第二个字符
- 删除字符串的最后一个字符
- 删除字符串的倒数第二个字符
我怎样才能精确地进行 K 次删除，以使最终字符串具有最小的字典顺序？
示例：
S=“蕉麻”，K=2
- 删除字符串的第二个字符
- 删除字符串的倒数第二个字符
最终字符串：“aacaaa”，这是可能的最小字典序。
P/S:
我已经试了很多天了，还是找不到解决这个问题的有效方法。不过我觉得跟动态规划有点关系。
有趣的任务！
更新：第 5 步不正确。这是正确的：
所有长度为 M 的组合，由第 3 次和第 4 次删除操作组成，等于此 class 操作：
零个或多个 3 在零个或多个 4 之后，像这样的正则表达式：(3)(4)
你可以证明：
- 43对等于33
- 343 对等于 443。
- 而且 34...43 等于 44...43。
所以你可以选择最右边的 3 并使用规则 3 使其成为唯一的 3。并使用规则 4 将所有左边的 4 转换为 3。
任意 -> 规则 3-> 4...434...4 -> 规则 1-> 3...34...4
这导致第6步暴力破解的复杂度为O(K^3)。
原回答
有一些想法和解决方案可以很好地共通
- [词越短越小]错了，如@n。 1.8e9-where's-my-share m.提示。所有可能的结果都将是等长的（Length-K），因为我们应该使用它们。
- 字典顺序是指：对于半长单词，我们从左到右匹配符号直到相等。单词比较的结果是第一个不同字符比较结果的结果。因此，对于所有正 j，第 i 个符号的最小化比第 (i+j) 个符号的最小化更重要。
- 所以最重要的是第一个符号最小化。只有第一次删除操作可以影响它。通过第一次删除操作，我们尝试将最小可能值放在首位（它将是前 K 个符号的最小值）。如果有一些位置的字母最少 - 我们会选择最左边的一个（我们不想删除多余的符号并丢失正确答案）。
- 现在最重要的是第二个字母。所以我们也想最小化它。我们将使其像算法的第 3 步一样。但是，我们使用 2'nd 删除操作，如果我们有一些最小的变体 - 我们将它们全部保存为 candidates.
- 所有长度为 M 的组合，由第 3 次和第 4 次删除操作组成，只等于 2 种组合：
- 所有操作都是第 4 个：44...44
- 所有操作都是第 4 个，但最后一个是 3：44...43。
所以对于每个候选人，我们只能检查两种可能性。
- 暴力破解所有 候选人 的两种可能性。找到最小值。
在通常情况下，该算法运行良好。但在最坏的情况下它很弱。有对位：具有相同字母的 Maxlength 字符串。然后我们有 K 个候选人，算法复杂度将为 O(K^2) - 这对这项任务不利。
为了处理它，我认为我们可以在算法的第 6 步选择合适的候选人：
6*。对于两个 候选人 - 比较他们的后缀 - 后面的字母。在相同尾部位置具有较小字母的候选者（尾部位置从该候选者头部位置算起）更适合我们的目的。
7*。比较算法第 5 步的两种可能性并选择最小值。
这种 (*) 方法的问题 - 我无法得到严格的证据证明它是更好的解决方案。最困难的部分是，当一个候选项是另一个候选项的前缀时——我们逐个字母地比较它，直到最小的不结束。例如在字符串 abcabcabc...abc 中，候选人位于第一和第四位置。
总的来说，这些想法应该会导致线性时间算法。
如果K≤N−4，则最终字符串至少有四个字符。它的双字符前缀是初始字符串的 (K+2) 个字符前缀的最少两个字符子序列。计算此前缀及其第二个字符的可能位置。这可以在 O(K) 时间内完成，方法是扫描前 K+2 个字符，保持到目前为止最少的字符和最少的两个字符子序列。
现在我们知道了两个字符的前缀，我们只需要确定最佳后缀。对于需要 J 次删除才能建立的前缀，最终字符串继续接下来的 N−4 − K 个我们不能触及的字符，然后是 (K+2 − J) 字符的最少两个字符的子序列初始字符串的后缀。我们可以使用前面描述的扫描算法计算每个相关后缀的最少两个字符的子序列。一个棘手的部分是有效地比较不可触及的中间部分。使用具有最长公共前缀的后缀数组可能会遇到一些困难。
如果 K > N−4，则 return 最少的 (N−K) 个字符子序列。
abcbaa 失败的非解决方案，K = 2
（感谢 גלעד ברקן 的 。）
- 在最低的基于 0 的索引 l1
的前 K+1 个元素中找到最小值
- 删除长度为 l1 的前缀（删除第一个 l1 次）- 如果 l1[=35= 则完成] = K
- 求1到1 + K - l1的元素中的最小值，包括l2
- “删除”从 1 到 l2 的元素（如果有）（删除第 2 个 l2 次）
- 从 l3 = 0 开始，而 K - l1 - l2 - l3 > 0,
删除最后两个元素中较大的一个并增加 l3
这是 Python 中的一个（希望如此）基本完整的解决方案（抱歉，我对 C++ 的精通程度更低）。我相信这个想法与 David Eisenstat 的想法相同或非常相似，他的回答帮助我更多地思考如何处理中间部分。中间部分的比较使用基于代码中引用和链接的后缀数组构造的 O(1) 查找和 O(n log n) 预处理（David 的建议是使用 O(n) 预处理和 O(1) 查找但是我还没有时间进入 O(1) RMQ 或 Ukkonen 的；我也被引用的 CP 后缀数组算法迷住了）。该代码包括与蛮力比较的测试，但不完整，因为它不处理只有前缀和后缀而没有中间的情况，无论如何处理起来应该更简单。可能有一些方法可以使代码更简洁和更有条理，但我还没有时间更仔细地考虑它。
因为我们可以删除第一个、第二个、倒数第二个或最后一个字符；解决方案的前两个字母将从 k 或更少删除后剩余的两个字母（子序列）中选择：
xxxAxxxxxxxB...
一旦我们通过删除一些第一个字符来确定字符 A，我们就只剩下 B 的选择了，这取决于我们对第二个字符进行了多少删除。显然，我们想要 A 的最低可用字符，我们可能有多个实例，然后是 B 的最低选择，我们也可能有多个实例。
后缀的组成类似，但我们需要为每个已为前缀选择的 k - num_deletions 存储最佳后缀。然后最终候选者是最低的两个字符前缀 + 中间 + 双字符后缀，其中中间由每个候选者中的删除分布固定。我们可以使用带有附加信息的后缀数组或树来比较中间值。
Python
def log2(n):
i = -1
while(n):
i += 1
n >>= 1
return i
# https://cp-algorithms.com/string/suffix-array.html
def sort_cyclic_shifts(s):
n = len(s)
alphabet = 256
cs = []
p = [0] * n
c = [0] * n
cnt = [0] * max(alphabet, n + 1)
for i in range(n):
cnt[ord(s[i])] += 1
for i in range(1, alphabet):
cnt[i] += cnt[i-1]
for i in range(n):
cnt[ord(s[i])] -= 1
p[cnt[ord(s[i])]] = i
c[p[0]] = 0
classes = 1
for i in range(1, n):
if s[p[i]] != s[p[i-1]]:
classes += 1
c[p[i]] = classes - 1
cs.append(c[:])
pn = [0] * n
cn = [0] * n
h = 0
while (1 << h) < n:
for i in range(n):
pn[i] = p[i] - (1 << h)
if pn[i] < 0:
pn[i] += n
for i in range(0, classes):
cnt[i] = 0
for i in range(n):
cnt[c[pn[i]]] += 1
for i in range(1, classes):
cnt[i] += cnt[i-1]
for i in range(n-1, -1, -1):
cnt[c[pn[i]]] -= 1
p[cnt[c[pn[i]]]] = pn[i]
cn[p[0]] = 0
classes = 1
for i in range(i, n):
cur = c[p[i]], c[(p[i] + (1 << h)) % n]
prev = c[p[i-1]], c[(p[i-1] + (1 << h)) % n]
if cur != prev:
classes += 1
cn[p[i]] = classes - 1
c = cn
cs.append(c[:])
h += 1
return p, cs
# https://cp-algorithms.com/string/suffix-array.html
def suffix_array_construction(s):
s += "$"
sorted_shifts, cs = sort_cyclic_shifts(s)
return sorted_shifts[1:], cs
# https://cp-algorithms.com/string/suffix-array.html
def compare(i, j, l, k, n, c):
a = c[k][i], c[k][(i+l-(1 << k))%n]
b = c[k][j], c[k][(j+l-(1 << k))%n]
if a == b:
return 0
elif a < b:
return -1
return 1
## MAIN FUNCTION
def f(s, k):
debug = 0
n = len(s)
# Best prefix
best_first = s[k]
best_second = s[k+1]
first_idxs = [k]
second_idxs = [k + 1]
for i in range(k - 1, -1, -1):
if s[i] <= best_first:
best_first = s[i]
# We only need one leftmost index
first_idxs = [i]
for i in range(k, first_idxs[0], -1):
if (s[i] < best_second):
best_second = s[i]
second_idxs = [i]
elif s[i] == best_second:
second_idxs.append(i)
second_idxs = list(reversed(second_idxs))
# Best suffix
# For each of l deletions,
# we can place the last
# character anywhere ahead
# of the penultimate.
last_idxs = {(n - 2): [n - 1]}
best_last = s[n - 1]
for l in range(2, k + 2):
idx = n - l
if s[idx] < best_last:
best_last = s[idx]
last_idxs[n - 1 - l] = [idx]
else:
last_idxs[n - 1 - l] = last_idxs[n - l]
p, cs = suffix_array_construction(s)
second_idx = 0
if debug:
print(first_idxs, second_idxs, last_idxs)
while first_idxs[0] >= second_idxs[second_idx]:
second_idx += 1
prefix_end = second_idxs[second_idx]
num_deleted = prefix_end - 1
remaining = k - num_deleted
suffix_start = n - remaining - 2
best = (prefix_end + 1, suffix_start - 1)
while second_idx < len(second_idxs):
prefix_end = second_idxs[second_idx]
num_deleted = prefix_end - 1
remaining = k - num_deleted
suffix_start = n - remaining - 2
len_candidate_middle = suffix_start - 1 - prefix_end
# The prefixes are all equal.
# We need to compare the middle
# and suffix.
# compare(i, j, l, k, n, c)
len_best_middle = best[1] - best[0] + 1
l = min(len_candidate_middle, len_best_middle)
# Compare middles
comp = compare(best[0], prefix_end + 1, l, log2(l), n + 1, cs)
# Candidate is better
if comp == 1:
best = (prefix_end + 1, suffix_start - 1)
elif comp == 0:
# Compare suffix of candidate with
# substring at the comparable position
# of best.
[last_idx] = last_idxs[suffix_start]
candidate_suffix = s[suffix_start] + s[last_idx]
if len_candidate_middle < len_best_middle:
# One character of best's suffix
if len_candidate_middle + 1 == len_best_middle:
to_compare = s[best[1]] + s[best[1] + 1]
# None of best's suffix
else:
idx = best[0] + len_candidate_middle
to_compare = s[idx] + s[idx + 1]
# If the candidate suffix is equal
# to best's equivalent, the candidate
# wins since it's shorter.
if candidate_suffix <= to_compare:
best = (prefix_end + 1, suffix_start - 1)
elif len_candidate_middle == len_best_middle:
idx = best[1] + 1
to_compare = s[idx] + s[last_idxs[idx][0]]
if candidate_suffix < to_compare:
best = (prefix_end + 1, suffix_start - 1)
# len_best_middle < len_candidate_middle
else:
# One character of candidate's suffix
if len_best_middle + 1 == len_candidate_middle:
to_compare = s[suffix_start - 1] + s[suffix_start]
# None of candidates's suffix
else:
idx = prefix_end + 1 + len_best_middle
to_compare = s[idx] + s[idx + 1]
if candidate_suffix < to_compare:
best = (prefix_end + 1, suffix_start - 1)
second_idx += 1
prefix = s[first_idxs[0]] + s[second_idxs[second_idx-1]]
middle = s[best[0]:best[1] + 1]
suffix = s[best[1] + 1] + s[last_idxs[best[1] + 1][0]]
return prefix + middle + suffix
def brute_force(s, k):
best = s + "z"
stack = [(s, k)]
while stack:
_s, _k = stack.pop()
if _k == 0:
best = min(best, _s)
continue
stack.append((_s[1:], _k - 1))
stack.append((_s[0] + _s[2:], _k - 1))
stack.append((_s[0:len(_s)-1], _k - 1))
stack.append((_s[0:len(_s)-2] + _s[-1], _k - 1))
return best
# 01234567
#s = "abacaaba"
#k = 2
# Test
import random
n = 12
num_tests = 500
for _ in range(num_tests):
s = "".join([chr(97 + random.randint(0, 25)) for i in range(n)])
k = random.randint(1, n - 5)
#print(s, k)
_f = f(s, k)
brute = brute_force(s, k)
if brute != _f:
print("MISMATCH!")
print(s, k)
print(_f)
print(brute)
break
print("Done.")
我会 post 这个答案，即使有一个公认的答案，因为我觉得所有其他答案都比他们需要的更复杂。下面是解决这个问题的 O(NK) 算法，如果使用后缀树进行“中间”部分的比较，可以“轻松”将其制成 O(N) 算法。
#!/usr/bin/python
def lex_kr(x,K,k_r):
"""
Get a lexicographically comparable subset of `x` for a given value of
`k_r`.
"""
N = len(x)
assert k_r > 0 and k_r < K # check for corner cases
k_l = K - k_r
v_l = min(x[:k_l+1])
v_r = min(x[-k_r-1:])
lex = [v_l]
lex += x[k_l+1:N-k_r-1]
lex += [v_r]
return lex
def lex_corner(x,K):
"""
Get the two lexicographically comparable subsets of `x` for corner cases
when `k_r=0` and `k_r=K`.
"""
N = len(x)
k_l = K
v_l = min(x[:k_l+1])
lex0 = [v_l]
lex0 += x[k_l+1:]
k_r = K
v_r = min(x[-k_r-1:])
lex1 = x[:N-k_r-1]
lex1 += [v_r]
return lex0,lex1
def min_lex(x,K):
subsets = [ lex_kr(x,K,k_r) for k_r in range(1,K) ]
subsets += lex_corner(x,K) # append the two corner cases
return min(subsets)
if __name__ == '__main__':
S = [ x for x in 'abacaaba' ]
K = 2
print(min_lex(S,K))
打印 ['a', 'a', 'c', 'a', 'a', 'a'].
数组左右（前缀&后缀）min的比较显然可以在函数lex_kr.[=中预计算O(N)时间16=]
中间部分（即 x[k_l+1:N-k_r-1]）需要一个聪明的技巧来有效地在字法上与所有其他中间部分进行比较。这可以在 O(1) 中完成，如其他答案（https://cp-algorithms.com/string/suffix-array.html) or a suffix automaton (https://cp-algorithms.com/string/suffix-automaton.html）中所述，每次比较使用 suffix-tree/array，后者更复杂但更有效。一旦实现，这将产生一个 O(N) 算法，与其他答案相比，需要检查的特殊情况更少。
问题：
给定一个字符串SS.length() <= 5.10^5和一个整数KK <= S.length()。对于每次删除，您可以：
- 删除字符串的第一个字符
- 删除字符串的第二个字符
- 删除字符串的最后一个字符
- 删除字符串的倒数第二个字符
我怎样才能精确地进行 K 次删除，以使最终字符串具有最小的字典顺序？
示例：
S=“蕉麻”，K=2
- 删除字符串的第二个字符
- 删除字符串的倒数第二个字符
最终字符串：“aacaaa”，这是可能的最小字典序。
P/S:
我已经试了很多天了，还是找不到解决这个问题的有效方法。不过我觉得跟动态规划有点关系。
有趣的任务！
更新：第 5 步不正确。这是正确的：
所有长度为 M 的组合，由第 3 次和第 4 次删除操作组成，等于此 class 操作： 零个或多个 3 在零个或多个 4 之后，像这样的正则表达式：(3)(4) 你可以证明：
- 43对等于33
- 343 对等于 443。
- 而且 34...43 等于 44...43。
所以你可以选择最右边的 3 并使用规则 3 使其成为唯一的 3。并使用规则 4 将所有左边的 4 转换为 3。
任意 -> 规则 3-> 4...434...4 -> 规则 1-> 3...34...4
这导致第6步暴力破解的复杂度为O(K^3)。
原回答
有一些想法和解决方案可以很好地共通
- [词越短越小]错了，如@n。 1.8e9-where's-my-share m.提示。所有可能的结果都将是等长的（Length-K），因为我们应该使用它们。
- 字典顺序是指：对于半长单词，我们从左到右匹配符号直到相等。单词比较的结果是第一个不同字符比较结果的结果。因此，对于所有正 j，第 i 个符号的最小化比第 (i+j) 个符号的最小化更重要。
- 所以最重要的是第一个符号最小化。只有第一次删除操作可以影响它。通过第一次删除操作，我们尝试将最小可能值放在首位（它将是前 K 个符号的最小值）。如果有一些位置的字母最少 - 我们会选择最左边的一个（我们不想删除多余的符号并丢失正确答案）。
- 现在最重要的是第二个字母。所以我们也想最小化它。我们将使其像算法的第 3 步一样。但是，我们使用 2'nd 删除操作，如果我们有一些最小的变体 - 我们将它们全部保存为 candidates.
- 所有长度为 M 的组合，由第 3 次和第 4 次删除操作组成，只等于 2 种组合：
- 所有操作都是第 4 个：44...44
- 所有操作都是第 4 个，但最后一个是 3：44...43。 所以对于每个候选人，我们只能检查两种可能性。
- 暴力破解所有 候选人 的两种可能性。找到最小值。
在通常情况下，该算法运行良好。但在最坏的情况下它很弱。有对位：具有相同字母的 Maxlength 字符串。然后我们有 K 个候选人，算法复杂度将为 O(K^2) - 这对这项任务不利。
为了处理它，我认为我们可以在算法的第 6 步选择合适的候选人：
6*。对于两个 候选人 - 比较他们的后缀 - 后面的字母。在相同尾部位置具有较小字母的候选者（尾部位置从该候选者头部位置算起）更适合我们的目的。
7*。比较算法第 5 步的两种可能性并选择最小值。
这种 (*) 方法的问题 - 我无法得到严格的证据证明它是更好的解决方案。最困难的部分是，当一个候选项是另一个候选项的前缀时——我们逐个字母地比较它，直到最小的不结束。例如在字符串 abcabcabc...abc 中，候选人位于第一和第四位置。
总的来说，这些想法应该会导致线性时间算法。
如果K≤N−4，则最终字符串至少有四个字符。它的双字符前缀是初始字符串的 (K+2) 个字符前缀的最少两个字符子序列。计算此前缀及其第二个字符的可能位置。这可以在 O(K) 时间内完成，方法是扫描前 K+2 个字符，保持到目前为止最少的字符和最少的两个字符子序列。
现在我们知道了两个字符的前缀，我们只需要确定最佳后缀。对于需要 J 次删除才能建立的前缀，最终字符串继续接下来的 N−4 − K 个我们不能触及的字符，然后是 (K+2 − J) 字符的最少两个字符的子序列初始字符串的后缀。我们可以使用前面描述的扫描算法计算每个相关后缀的最少两个字符的子序列。一个棘手的部分是有效地比较不可触及的中间部分。使用具有最长公共前缀的后缀数组可能会遇到一些困难。
如果 K > N−4，则 return 最少的 (N−K) 个字符子序列。
abcbaa 失败的非解决方案，K = 2
（感谢 גלעד ברקן 的
- 在最低的基于 0 的索引 l1 的前 K+1 个元素中找到最小值
- 删除长度为 l1 的前缀（删除第一个 l1 次）- 如果 l1[=35= 则完成] = K
- 求1到1 + K - l1的元素中的最小值，包括l2
- “删除”从 1 到 l2 的元素（如果有）（删除第 2 个 l2 次）
- 从 l3 = 0 开始，而 K - l1 - l2 - l3 > 0,
删除最后两个元素中较大的一个并增加 l3
这是 Python 中的一个（希望如此）基本完整的解决方案（抱歉，我对 C++ 的精通程度更低）。我相信这个想法与 David Eisenstat 的想法相同或非常相似，他的回答帮助我更多地思考如何处理中间部分。中间部分的比较使用基于代码中引用和链接的后缀数组构造的 O(1) 查找和 O(n log n) 预处理（David 的建议是使用 O(n) 预处理和 O(1) 查找但是我还没有时间进入 O(1) RMQ 或 Ukkonen 的；我也被引用的 CP 后缀数组算法迷住了）。该代码包括与蛮力比较的测试，但不完整，因为它不处理只有前缀和后缀而没有中间的情况，无论如何处理起来应该更简单。可能有一些方法可以使代码更简洁和更有条理，但我还没有时间更仔细地考虑它。
因为我们可以删除第一个、第二个、倒数第二个或最后一个字符；解决方案的前两个字母将从 k 或更少删除后剩余的两个字母（子序列）中选择：
xxxAxxxxxxxB...
一旦我们通过删除一些第一个字符来确定字符 A，我们就只剩下 B 的选择了，这取决于我们对第二个字符进行了多少删除。显然，我们想要 A 的最低可用字符，我们可能有多个实例，然后是 B 的最低选择，我们也可能有多个实例。
后缀的组成类似，但我们需要为每个已为前缀选择的 k - num_deletions 存储最佳后缀。然后最终候选者是最低的两个字符前缀 + 中间 + 双字符后缀，其中中间由每个候选者中的删除分布固定。我们可以使用带有附加信息的后缀数组或树来比较中间值。
Python
def log2(n):
i = -1
while(n):
i += 1
n >>= 1
return i
# https://cp-algorithms.com/string/suffix-array.html
def sort_cyclic_shifts(s):
n = len(s)
alphabet = 256
cs = []
p = [0] * n
c = [0] * n
cnt = [0] * max(alphabet, n + 1)
for i in range(n):
cnt[ord(s[i])] += 1
for i in range(1, alphabet):
cnt[i] += cnt[i-1]
for i in range(n):
cnt[ord(s[i])] -= 1
p[cnt[ord(s[i])]] = i
c[p[0]] = 0
classes = 1
for i in range(1, n):
if s[p[i]] != s[p[i-1]]:
classes += 1
c[p[i]] = classes - 1
cs.append(c[:])
pn = [0] * n
cn = [0] * n
h = 0
while (1 << h) < n:
for i in range(n):
pn[i] = p[i] - (1 << h)
if pn[i] < 0:
pn[i] += n
for i in range(0, classes):
cnt[i] = 0
for i in range(n):
cnt[c[pn[i]]] += 1
for i in range(1, classes):
cnt[i] += cnt[i-1]
for i in range(n-1, -1, -1):
cnt[c[pn[i]]] -= 1
p[cnt[c[pn[i]]]] = pn[i]
cn[p[0]] = 0
classes = 1
for i in range(i, n):
cur = c[p[i]], c[(p[i] + (1 << h)) % n]
prev = c[p[i-1]], c[(p[i-1] + (1 << h)) % n]
if cur != prev:
classes += 1
cn[p[i]] = classes - 1
c = cn
cs.append(c[:])
h += 1
return p, cs
# https://cp-algorithms.com/string/suffix-array.html
def suffix_array_construction(s):
s += "$"
sorted_shifts, cs = sort_cyclic_shifts(s)
return sorted_shifts[1:], cs
# https://cp-algorithms.com/string/suffix-array.html
def compare(i, j, l, k, n, c):
a = c[k][i], c[k][(i+l-(1 << k))%n]
b = c[k][j], c[k][(j+l-(1 << k))%n]
if a == b:
return 0
elif a < b:
return -1
return 1
## MAIN FUNCTION
def f(s, k):
debug = 0
n = len(s)
# Best prefix
best_first = s[k]
best_second = s[k+1]
first_idxs = [k]
second_idxs = [k + 1]
for i in range(k - 1, -1, -1):
if s[i] <= best_first:
best_first = s[i]
# We only need one leftmost index
first_idxs = [i]
for i in range(k, first_idxs[0], -1):
if (s[i] < best_second):
best_second = s[i]
second_idxs = [i]
elif s[i] == best_second:
second_idxs.append(i)
second_idxs = list(reversed(second_idxs))
# Best suffix
# For each of l deletions,
# we can place the last
# character anywhere ahead
# of the penultimate.
last_idxs = {(n - 2): [n - 1]}
best_last = s[n - 1]
for l in range(2, k + 2):
idx = n - l
if s[idx] < best_last:
best_last = s[idx]
last_idxs[n - 1 - l] = [idx]
else:
last_idxs[n - 1 - l] = last_idxs[n - l]
p, cs = suffix_array_construction(s)
second_idx = 0
if debug:
print(first_idxs, second_idxs, last_idxs)
while first_idxs[0] >= second_idxs[second_idx]:
second_idx += 1
prefix_end = second_idxs[second_idx]
num_deleted = prefix_end - 1
remaining = k - num_deleted
suffix_start = n - remaining - 2
best = (prefix_end + 1, suffix_start - 1)
while second_idx < len(second_idxs):
prefix_end = second_idxs[second_idx]
num_deleted = prefix_end - 1
remaining = k - num_deleted
suffix_start = n - remaining - 2
len_candidate_middle = suffix_start - 1 - prefix_end
# The prefixes are all equal.
# We need to compare the middle
# and suffix.
# compare(i, j, l, k, n, c)
len_best_middle = best[1] - best[0] + 1
l = min(len_candidate_middle, len_best_middle)
# Compare middles
comp = compare(best[0], prefix_end + 1, l, log2(l), n + 1, cs)
# Candidate is better
if comp == 1:
best = (prefix_end + 1, suffix_start - 1)
elif comp == 0:
# Compare suffix of candidate with
# substring at the comparable position
# of best.
[last_idx] = last_idxs[suffix_start]
candidate_suffix = s[suffix_start] + s[last_idx]
if len_candidate_middle < len_best_middle:
# One character of best's suffix
if len_candidate_middle + 1 == len_best_middle:
to_compare = s[best[1]] + s[best[1] + 1]
# None of best's suffix
else:
idx = best[0] + len_candidate_middle
to_compare = s[idx] + s[idx + 1]
# If the candidate suffix is equal
# to best's equivalent, the candidate
# wins since it's shorter.
if candidate_suffix <= to_compare:
best = (prefix_end + 1, suffix_start - 1)
elif len_candidate_middle == len_best_middle:
idx = best[1] + 1
to_compare = s[idx] + s[last_idxs[idx][0]]
if candidate_suffix < to_compare:
best = (prefix_end + 1, suffix_start - 1)
# len_best_middle < len_candidate_middle
else:
# One character of candidate's suffix
if len_best_middle + 1 == len_candidate_middle:
to_compare = s[suffix_start - 1] + s[suffix_start]
# None of candidates's suffix
else:
idx = prefix_end + 1 + len_best_middle
to_compare = s[idx] + s[idx + 1]
if candidate_suffix < to_compare:
best = (prefix_end + 1, suffix_start - 1)
second_idx += 1
prefix = s[first_idxs[0]] + s[second_idxs[second_idx-1]]
middle = s[best[0]:best[1] + 1]
suffix = s[best[1] + 1] + s[last_idxs[best[1] + 1][0]]
return prefix + middle + suffix
def brute_force(s, k):
best = s + "z"
stack = [(s, k)]
while stack:
_s, _k = stack.pop()
if _k == 0:
best = min(best, _s)
continue
stack.append((_s[1:], _k - 1))
stack.append((_s[0] + _s[2:], _k - 1))
stack.append((_s[0:len(_s)-1], _k - 1))
stack.append((_s[0:len(_s)-2] + _s[-1], _k - 1))
return best
# 01234567
#s = "abacaaba"
#k = 2
# Test
import random
n = 12
num_tests = 500
for _ in range(num_tests):
s = "".join([chr(97 + random.randint(0, 25)) for i in range(n)])
k = random.randint(1, n - 5)
#print(s, k)
_f = f(s, k)
brute = brute_force(s, k)
if brute != _f:
print("MISMATCH!")
print(s, k)
print(_f)
print(brute)
break
print("Done.")
我会 post 这个答案，即使有一个公认的答案，因为我觉得所有其他答案都比他们需要的更复杂。下面是解决这个问题的 O(NK) 算法，如果使用后缀树进行“中间”部分的比较，可以“轻松”将其制成 O(N) 算法。
#!/usr/bin/python
def lex_kr(x,K,k_r):
"""
Get a lexicographically comparable subset of `x` for a given value of
`k_r`.
"""
N = len(x)
assert k_r > 0 and k_r < K # check for corner cases
k_l = K - k_r
v_l = min(x[:k_l+1])
v_r = min(x[-k_r-1:])
lex = [v_l]
lex += x[k_l+1:N-k_r-1]
lex += [v_r]
return lex
def lex_corner(x,K):
"""
Get the two lexicographically comparable subsets of `x` for corner cases
when `k_r=0` and `k_r=K`.
"""
N = len(x)
k_l = K
v_l = min(x[:k_l+1])
lex0 = [v_l]
lex0 += x[k_l+1:]
k_r = K
v_r = min(x[-k_r-1:])
lex1 = x[:N-k_r-1]
lex1 += [v_r]
return lex0,lex1
def min_lex(x,K):
subsets = [ lex_kr(x,K,k_r) for k_r in range(1,K) ]
subsets += lex_corner(x,K) # append the two corner cases
return min(subsets)
if __name__ == '__main__':
S = [ x for x in 'abacaaba' ]
K = 2
print(min_lex(S,K))
打印 ['a', 'a', 'c', 'a', 'a', 'a'].
数组左右（前缀&后缀）min的比较显然可以在函数lex_kr.[=中预计算O(N)时间16=]
中间部分（即 x[k_l+1:N-k_r-1]）需要一个聪明的技巧来有效地在字法上与所有其他中间部分进行比较。这可以在 O(1) 中完成，如其他答案（https://cp-algorithms.com/string/suffix-array.html) or a suffix automaton (https://cp-algorithms.com/string/suffix-automaton.html）中所述，每次比较使用 suffix-tree/array，后者更复杂但更有效。一旦实现，这将产生一个 O(N) 算法，与其他答案相比，需要检查的特殊情况更少。