从列表中选择所有字符串的最快方法

Question

我正在寻找从一组字符开始查找集合中所有字符串的最快方法.我可以使用排序集合,但是我找不到在.net中执行此操作的便捷方法.基本上我需要在符合条件的集合中找到低和高索引.

列表<T>上的二进制搜索不保证返回的索引是第一个元素的索引,因此需要上下迭代以查找所有匹配的字符串,如果有一个大的列表则不会很快.

还有Linq方法(并行),但我不确定哪种数据结构会提供最好的结果.

列表示例,~10M记录:

aaaaaaaaaaaaaaabb
aaaaaaaaaaaaaaba
aaaaaaaaaaaaabc
...
zzzzzzzzzzzzzxx
zzzzzzzzzzzzzyzzz
zzzzzzzzzzzzzzzzzza

从以下字符开始搜索字符串:skk ...

结果:记录从x到y的索引.

更新:字符串可以具有不同的长度并且是唯一的.

Answer 1

就时间复杂度而言 - 你应该使用trie，而不是排序集或二分搜索。

Trie 会给你一个O(|S|)时间复杂度[而排序集和二分搜索会让你O(|S|logn)]找到节点[让它成为v]。

trie 中符合前缀的所有字符串 [paths] 将通过v. 通过增加numberOfLeaves字段，您可以准确地查出该节点有多少个叶子[=strings]。

在一次传递中 - 您还可以找到此v[对于u从根到的路径中的每个节点v-numberOfLeaves剩余的每个同级的总和u]。

与使用现有结构相比，这需要做更多的工作，但如果数据很大 - 它可以使您的算法更快，因此如果性能是一个问题并且您期望有大量字符串，您应该考虑它。