这里有一种获取第i个字符串起始字符的方法:
s = "robert"
cumulative = 0
for c,num in sorted((j,i+1) for i,j in enumerate(reversed(s))):
print c,num,cumulative
cumulative+=x
b 4 0
e 3 4
o 5 7
r 2 12
r 6 14
t 1 20
现在从上面的结果中(可以快速生成),您可以看到从累计值中,如果 i 在 0 和 4 之间,我们应该使用 'b' 作为第一个字符。如果 i 在 7 和 12 之间,我们将使用 'o' 作为第一个字符,依此类推。
要验证这一点,我们可以查看有序的子字符串(注意,在 7 和 12 之间,它们都以 'o' 开头)(从索引 0 开始,包括 7,不包括 12):
print sorted([s[a:b] for a in range(n+1) for b in range(a+1,n+2)])
['b', 'be', 'ber', 'bert', 'e', 'er', 'ert', 'o', 'ob', 'obe', 'ober', 'obert', 'r', 'r', 'ro', 'rob', 'robe', 'rober', 'robert', 'rt', 't']
现在,您可以使用此技术来获取第一个字符。一旦您拥有
第一个字符,您就可以从累积值中知道已经经过了多少子字符串。我们可以从i中减去这个累积值。现在,我们看一个新的字符串,它是从
第一个(先前选择的)字符开始(不包括第一个字符)。我们再次应用相同的技术(使用新字符串和新i值)以获取第二个字符。
希望这有意义。祝好运。
s
中任意连续字符的子集,那么确实有O(n^2)个这样的字符串。你需要研究多少个索引i
呢?我猜你只需要一个固定数量的i
(例如1),因为如果你需要所有可能的索引,那么计算时间需要对所有子串进行排序,这需要O(n^2 log n)的时间而不是O(n^2)。这个猜测正确吗? - Eric O. Lebigot