什么是STARTwith和/或包含搜索的最快的字符串集合结构/算法

Question

我有以下情况:我有一大堆字符串(比方说250.000+)平均长度可能为30.我要做的就是在这些内部进行很多搜索...大多数是StartsWith和Contains类型.

该集合在运行时是静态的.这意味着初始读数和填充选择只进行一次.因此,构建数据结构的性能绝对不重要.内存也不是问题:这也意味着我不介意在需要时有两个具有相同数据的集合(例如一个用于startswith而另一个用于contains).唯一重要的是搜索的性能,它应返回与搜索条件匹配的所有元素.

首先,我遇到了Trie或Radix-tree ..但也许还有更好的选择？

对于contains ..我根本没有任何好主意(除了在列表上运行linq查询时,该数据量不会非常快).

在此先感谢大家!

更新:我忘记了一个重要的部分:使用Contains我的意思是集合中没有完全匹配..但我想找到集合中包含给定searchstring的所有字符串

Answer 1

构建后缀树将允许您在O(1). 我的迂腐情不自禁地注意到，它实际上O(n + m)是与n您的子字符串匹配的字符串的数量，以及m正在查询的子字符串的大小。

那么你问的后缀树是什么？在其最基本的实现中，它是一个具有更奇特的插入方法的特里树：除了添加字符串之外，它还将该字符串的每个可能的后缀添加到特里树中。在这个数据结构上，子字符串搜索变成了所有可能的后缀的前缀搜索。由于您还想进行前缀搜索，因此您需要在每个插入的字符串和查询子字符串前面添加一个特殊字符。特殊字符将允许您区分后缀和完整字符串。

虽然后缀树的这种实现非常简单，但效率也非常低（O(n^2)空间和构建时间）。幸运的是，还有其他更有效的实现可以大大减少空间和时间限制。其中之一，Ukkonen 算法，在这个 SO 答案中得到了很好的解释，并将空间限制降低到O(n)。您可能还想研究后缀数组，它是后缀树的等效但更有效的表示。

虽然我知道还有更多后缀树的实现（其中之一可能会满足您的用例），但我只是不了解它们。我建议您在决定实施之前对该主题进行一些研究。