字符串的子串的顺序统计量

Question

我有一个长度为n的长字符串s和一个整数i。我想知道s的第i个子串在字典序下的顺序。

朴素的方法是创建s的所有子串的集合，然后获取该集合的第i个顺序统计量。这种方法需要O(n^2)时间，但构建s的所有子串的集合太耗费内存了。

是否有一种更"内存友好"的方法？

- Randomblue

---

如果你所说的“子串”是指输入字符串s中任意连续字符的子集，那么确实有O(n^2)个这样的字符串。你需要研究多少个索引i呢？我猜你只需要一个固定数量的i（例如1），因为如果你需要所有可能的索引，那么计算时间需要对所有子串进行排序，这需要O(n^2 log n)的时间而不是O(n^2)。这个猜测正确吗？ - Eric O. Lebigot

@EOL 在大小为n的列表中查找元素的标准快速选择算法是O(n)，而不是O(n log(n))。 - btilly

@btilly：确实。O(n^2 log n)是对所有子字符串（朴素地）进行排序的时间复杂度，而不是仅针对单个i查找第i个字符串的O(n^2)。 - Eric O. Lebigot

Answer 1

一个字符串的子串是该字符串的后缀的前缀。您可以使用在http://en.wikipedia.org/wiki/Suffix_array中提到的算法之一，在O(n)时间内获得已排序的后缀列表。Juha Kärkkäinen和Peter Sanders（2003）提到的算法很简单，可以实现线性工作的后缀数组构建。

从已排序的后缀列表中，您可以使用某种懒惰合并方案，获得已排序的后缀的前缀列表=已排序的子字符串列表。

- mcdowella

Answer 2

这里有一种获取第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值）以获取第二个字符。

希望这有意义。祝好运。

- Rusty Rob

---

@Randomblue，这对你有意义吗？ - Rusty Rob

如果存在重复字符，则会增加一个复杂度。您需要检查每个重复字符的子字符串重叠的程度。 - Rusty Rob