当前位置：文江博客话题详情

字符串子串的顺序统计

发布于 2025-01-08 14:49:52 字数 232 浏览 1 评论 0原文

我有一个大小为 n 的长字符串 s 和一个整数 i。我对字典顺序下 s 的第 i 个子字符串感兴趣。

简单的方法是创建 s 的所有子串的集合，然后获取该集合的第 i 个阶统计量。这种方法需要 O(n^2) 时间，但构造 s 的所有子字符串的集合过于占用内存。

有没有更“记忆友好”的方法？

原文

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

氛圍 2025-01-15 14:49:52

子字符串是字符串后缀的前缀。您可以使用 http:// 中提到的算法之一在 O(n) 时间内获得后缀的排序列表。 /en.wikipedia.org/wiki/Suffix_array。 Juha Kärkkäinen 和 Peter Sanders (2003) 中提到的这一点。 “简单的线性工作后缀数组构造相当简单。

从后缀的排序列表中，某种惰性合并方案应该为您提供后缀前缀的排序列表 = 子字符串的排序列表。

回复收藏 0 原文

深海少女心 2025-01-15 14:49:52

下面是获取第 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 值）来获取第二个字符。

希望这是有道理的。祝你好运。

Here is a way of getting the starting character of the ith string:

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

Now from the results above (which can be generated quickly), you can see from the cumulative value that if i is between 0 and 4, we should use 'b' as the first character.
If i was between 7 and 12, we would use 'o' as the first character and so on.

To verify this we can look at the ordered sub strings (see that between 7 and 12 they all start with 'o') (starting with index 0, inclusive of the 7, exclusive of the 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']

Now You can use this technique to get the first character. Once you have the first character, You know from the cumulative value how many substrings you have gone past. We can subtract this cumulative value from i. Now we look at a new string which is from the first (previously selected) character onwards (excluding the first character). We apply the same technique again (with the new string and the new i value) to get the second character.

Hopefully this makes sense. Good luck.

回复收藏 0 原文

~没有更多了~