问题：
给定一个字符串SS.length() <= 5.10^5和一个整数K CCD_。对于每次删除，您可以：
- 删除字符串的第一个字符
- 删除字符串的第二个字符
- 删除字符串的最后一个字符
- 删除字符串的倒数第二个字符
我如何才能精确地去除K，从而使最终字符串具有最小的字典顺序？
示例：
S＝"；abacaaba"；，K=2
- 删除字符串的第二个字符
- 删除字符串的倒数第二个字符
最后一个字符串："aacaaa"；这是尽可能小的词典学。
p/S:
我已经试了很多天了，但还是想不出一个有效的方法来解决这个问题。但我认为这与动态编程有关。
所有这些想法加在一起，应该会产生线性时间算法。
如果K≤N−4，则最后一个字符串至少有四个字符。它的两个字符前缀是初始字符串的(K+2)个字符前缀的最少两个字符的子序列。计算该前缀及其第二个字符的可能位置。这可以在O(K)时间内通过扫描前K+2个字符来实现，保持迄今为止最少的字符和迄今为止最少两个字符的子序列。
既然我们知道了两个字符的前缀，我们只需要确定最好的后缀。对于需要J个删除才能设置的前缀，最后一个字符串继续使用我们不能接触的下一个N−4−K字符，然后是初始字符串的(K+2−J)字符后缀的至少两个字符的子序列。我们可以使用前面描述的扫描算法来计算每个相关后缀的至少两个字符的子序列。一个棘手的部分是有效地比较不可触碰的中间人。这可以通过使用具有最长公共前缀的后缀数组来实现，但会遇到一些困难。
如果K>N−4，只返回最少(N−K)个字符的子序列。
有趣的任务！
更新：步骤5不正确。以下是正确的一个：
由第3个和第4个移除操作组成的所有长度为M的组合都等于此类操作：零或更多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-我在哪里。所有可能的结果都是相等的长度(length-K)，因为我们应该使用所有的结果
- 词汇顺序意味着：对于半长单词，我们从左到右匹配符号，直到符号相等。单词比较的结果是第一个不同字符比较的结果。因此，对于所有正j，第i个符号的最小化比第(i+j)个符号的最小更重要
- 所以最重要的是第一符号最小化。只有第一次移除操作才能影响它。通过第一次移除运算，我们试图将最小可能值放在第一位(它将是前K个符号中的最小值)。如果有一些位置的字母最小，我们会选择最左边的一个(我们不想删除多余的符号并丢失正确答案)
- 现在最重要的是第二个字母。所以我们也想把它最小化。我们将在算法的第3步中使其类似。但是，我们使用2'nd移除操作，如果我们有一些变体是最小的，我们将所有变体保存为候选者
- 由第3次和第4次移除操作组成的所有长度为M的组合仅等于2个组合：
- 所有操作都是第4个：44…44
- 所有操作都是第4次，但最后一次是3:44…43。因此，对于每个候选，我们只能检查两种可能性
- 用两种可能性对所有候选人进行粗暴对待。找到最小值
在常见情况下，该算法运行良好。但在最坏的情况下，它很弱。有对位法：相同字母的最大长度字符串。然后我们有K候选者，算法复杂度将为O(K^2)——这对这个任务不好。
为了处理它，我认为我们可以在算法的第6步选择正确的候选者：
6*。对于两个候选者-比较它们的后缀-后面的字母。在相同的尾部位置(尾部位置从该候选者的头部位置开始计数)具有较小字母的候选者更适合我们的目的。
7*。比较第5个算法步骤的两种可能性，并选择最小值。
这个(*)方法的问题——我无法得到一个确切的证据来证明它是更好的解决方案。最困难的是，当一个候选者是另一个候选者的前缀时，我们会逐个比较，直到最小的候选者并没有结束。例如字符串abcabcabc。。。abc，候选人在第一和第四位。
这里有一个(希望)基本上完整的Python解决方案(对不起，我对C++更不熟悉)。我相信这个想法与大卫·艾森斯塔特的想法相同或非常相似，他的回答帮助我更多地思考如何处理中场。中间部分的比较使用O(1)查找和基于代码中引用和链接的后缀数组结构的O(n-logn)预处理(David的建议是使用O(n)预预处理和O(1；我也被引用的CP后缀数组算法迷住了)。该代码包括与蛮力进行比较的测试，但它是不完整的，因为它不能处理只有前缀和后缀而没有中间的情况，无论如何，这应该更容易处理。可能有一些方法可以使代码更简洁、更有条理，但我还没有时间仔细考虑。
由于我们可以删除第一个、第二个、倒数第二个或最后一个字符；解决方案的前两个字母将从删除k或更少后剩余的两个字母(一个子序列)中选择：
xxxAxxxxxxxB...
一旦我们通过删除一些第一个字符来承诺字符A，我们就只能根据对第二个字符的删除次数来选择B。很明显，我们想要A的最低可用字符，我们可能有不止一个实例，然后是B的最低选择，我们也可能有不止的一个实例。
后缀的组成类似，但我们需要为每个已经为前缀选择的k-num_deleteions存储最佳后缀。那么最终的候选者是最低的两个字符前缀+中间+两个字符后缀，其中中间由每个候选者中的删除分布来固定。我们可以使用后缀数组或带有附加信息的树来比较中间值。
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.")
abcbaa的非解决方案失败，K=2
(共享测试值得称赞。)
- 在最低的基于0的索引l1的第一个K+1元素中找到最小值
- 删除长度为l1的前缀(删除第一个l1次)-如果l_1=K
- 求元素从1到1的最小值+K-l1，包括l2
- "删除"；从1到l2的元素(如果有)(删除第二次l2)
- 从l3=0开始，而K-l1-l2-l3>0，
删除最后两个元素中较大的一个，并增加l3
即使有公认的答案，我也会发布这个答案，因为我觉得所有其他答案都比它们需要的更复杂。下面是一个解决这个问题的O(NK)算法，它可以"容易"；如果后缀树被用来进行"N"的比较，则可以被制成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))
其打印CCD_ 3。
数组的左右(前缀和后缀)的min的比较显然可以在函数lex_kr中在O(N)时间内预先计算。
中间部分(即x[k_l+1:N-k_r-1])需要一个巧妙的技巧来有效地与所有其他中间部分进行文字比较。这可以使用其他答案中描述的后缀树/数组在每次比较的O(1)中完成(https://cp-algorithms.com/string/suffix-array.html)或后缀自动机(https://cp-algorithms.com/string/suffix-automaton.html)后者更复杂但更有效。一旦实现，这将产生O(N)算法，与其他答案相比，需要检查的特殊情况更少。