如何(快速)找到c# /. net中最长的匹配字符串?

本文关键字：字符串 net 快速 找到 如何 | 更新日期: 2023-09-27 18:16:07

我需要对一组项做一些查找操作。

首先我需要看看是否有直接匹配。这很简单，因为我有一个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

是否有类在框架中有哈希或树结构的后台实现做这样的事情，或者我需要自己写一些东西?

编辑到目前为止，我所拥有的是按模式字符串长度排序的列表，然后我一个接一个地查看条目，以查看查询是否从记录开始。这在大多数情况下都可以工作，因为我们还没有大的列表，但是在没有匹配的情况下，成本很高。

我没有足够的词汇量让谷歌给我一些与哈希集、列表和字典无关的页面。我发现所有的研究都指向基于树的结构，但没有一个指出是否已经在。net框架中实现了。

如何(快速)找到c# /. net中最长的匹配字符串?

Leppie and Spender是正确的;如果数据集变得很大，你想要实现的有效解决这个问题的数据结构是一个"trie"，或者，如果你真的很熟练，一个DAWG——一个有向无循环词图。如果字符串有许多常见后缀，则DAWG具有更好的内存性能，但它们更昂贵且难以构建和更新，因此从trie开始。

您的简单案例将生成如下所示的树:

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

所以要查找023456，你从根开始，沿着标记为0的分支找到A，然后沿着分支2找到B，那里没有分支3，所以你完成了。

顺便说一下，这也是你在给定字典和一组字母的情况下查找最长的Scrabble单词时使用的数据结构;这其实是同一个问题。

. net框架中没有内置的trie数据结构，但它不是一个很难构建的数据结构。我这里有一个不可变的trie，我一直想在博客上写一下;如果我有机会的话，我会在这里发布一个链接。

一个相当简单的方法是brute force他们。我假设您有一个Dictionary<string, string> _lookupTable来保存查找

string Find(string query)
{
    var retval = null;
    while(!string.IsNullOrEmpty(query) && retval == null)
    {
        if(!_lookupTable.TryGetValue(query, out retval))
            query = query.Substring(0, query.Length-1);
    }
    return retval;
}

你可以扫描整个字典寻找最长的匹配

        string sQuery = "01234";
        int iMaxLength = 0;
        foreach (KeyValuePair<String, String> kVP in mD)
        {
            if (sQuery.Contains(kVP.Value) && (kVP.Value.Length > iMaxLength))
            {
                iMaxLength = kVP.Value.Length
                result = (whatever...)
            }
        }

看起来，您应该使用简单地按长度排序的二叉树，然后查找第一个匹配。我不认为像二叉树这样的东西已经在c#中实现了，但是快速搜索一下就会发现很多网站已经这样做了。

相关文章：