如何（快速）找到 C#/.Net 中最长的匹配字符串

我需要对一组项目执行一些查找操作。

首先我需要看看是否有直接匹配。这很简单，因为我有一个条目Dictionary<String,MyObjectType>，这样我就可以走了dictionary["valuetofind"].

但是，如果没有直接匹配，那么我需要进行开始匹配，但它必须是返回的最长匹配：

记录示例：

String   Record
0        A
01       B
012      D
02       B
03       C

查询示例：

Query         Result 
0             A    - Because 0   is the longest match
01            B    - Because 01  is the longest match
023456        B    - Because 02  is the longest match
012           D    - Because 012 is the longest match
0123456       D    - Because 012 is the longest match
03456         C    - Because 03  is the longest match
04            A    - Because 0   is the longest match
0456          A    - Because 0   is the longest match
1             Null - No Match

框架中是否有类在后台实现中具有哈希或树结构来执行类似的操作，或者我需要自己编写一些东西？

EDIT到目前为止，我所拥有的是按模式字符串的长度排序的列表，然后我逐一检查条目以查看查询是否以记录开头。这对于大多数情况都有效，因为我们还没有大型列表，但对于没有匹配的情况，确实会产生昂贵的成本。

我缺乏词汇量，无法让谷歌为我提供与哈希集、列表和字典无关的页面。我发现的所有研究都指向基于树的结构，但没有指出 .NET Framework 中是否已经有实现。

莱皮和斯彭德是正确的；如果数据集变大，您想要实现有效解决此问题的数据结构是“trie”，或者，如果您真的很牛，则可以使用 DAWG——有向非循环字图。如果字符串具有许多常见后缀，则 DAWG 具有更好的内存性能，但它们更昂贵且难以构建和更新，因此从 trie 开始。

您的简单案例将创建一个如下所示的特里树：

           ROOT
            |
           0|
            |
            A
          / | \
         /  |  \
       1/  2|  3\
       /    |    \
      /     |     \
     B      B      C
     |
    2|
     |
     D

因此，要查找 023456，您从根开始，沿着标记为 0 的分支查找 A，然后沿着分支 2 查找 B，此时没有分支 3，所以您就完成了。

顺便说一句，这也是您在给定字典和一组字母的情况下查找最长拼字游戏单词的数据结构；这本质上是同一个问题。

.NET 框架中没有内置 trie 数据结构，但它并不是一个难以构建的数据结构。我有一个不可变的特里树躺在这里的某个地方，我一直想在博客中介绍它；如果我这样做，我会在这里发布一个链接。