我有以下情况：我有一大堆平均长度可能为 30 的字符串（比如说 250.000+）。我要做的是在这些字符串中进行很多搜索.. 大部分都是 StartsWith 和 Contains 类型的。
该集合在运行时是静态的。这意味着选择集合的初始读取和填充只进行一次..因此构建数据结构的性能绝对不重要。内存也不是问题：这也意味着如果需要，我不介意在每个集合中有两个具有相同数据的集合（比如一个用于startswith，另一个用于包含）。唯一重要的是搜索的性能，它应该返回与搜索条件匹配的所有元素。
首先，我遇到了 Trie 或 Radix-tree .. 但也许还有更好的选择？
For contains .. 我还没有好主意（除了在列表上运行 linq 查询，该列表不会很快处理大量数据）。
提前谢谢大家！
更新：我忘记了一个重要部分：使用包含我的意思是集合中没有完全匹配..但我想找到集合中包含给定搜索字符串的所有字符串
构建后缀树将允许您对所有字符串并行进行子字符串搜索O(1)。我的书呆子不禁注意到，与您的子字符串匹配的字符串数量以及被查询的子字符串的大小实际上O(n + m)在哪里。nm
那么你问的后缀树是什么？在其最基本的实现中，它是一个带有更高级插入方法的 trie：除了添加字符串之外，它还将该字符串的所有可能后缀添加到 trie。在这个数据结构上，子串搜索变成了所有可能后缀的前缀搜索。由于您还想进行前缀搜索，因此您需要在每个插入的字符串和查询子字符串的前面添加一个特殊字符。特殊字符将允许您区分后缀和完整字符串。
虽然后缀树的这种实现非常简单，但它也非常低效（O(n^2)空间和构建时间）。幸运的是，还有其他更有效的实现可以大大减少空间和时间限制。其中之一，Ukkonen 的算法，在这个 SO 答案中得到了很好的解释，并将空间限制到O(n). 您可能还想研究后缀数组，它们是后缀树的等效但更有效的表示。
虽然我知道还有更多后缀树的实现（其中一个可能会达到您的用例的最佳位置），但我只是不知道它们。我建议您在确定实施之前对该主题进行一些研究。