C# WinForms中如何高效搜索ListBox项是否存在于长字符串中？

你当前的代码在处理20万+项时会遇到严重的性能问题，核心瓶颈有两个：

1. 字符串拼接用+操作：每次拼接都会生成新的字符串实例，20万次操作会产生大量临时对象，GC压力陡增，执行速度极慢。
2. 逐个调用Result.Contains(itm)：每次都是对长字符串做线性扫描，时间复杂度为O(N*M)（N是项数，M是长字符串长度），20万次扫描的耗时会非常夸张。

下面针对不同场景给出优化方案：

场景1：待匹配项是长字符串中的独立元素 #

如果Result里的内容是用逗号、空格这类分隔符拆分的独立元素，先把Result转成哈希集合，将查找操作的时间复杂度降到O(1)，同时用StringBuilder处理拼接：

// 根据实际分隔符拆分Result，这里假设是逗号
var resultElements = new HashSet<string>(Result.Split(',', StringSplitOptions.RemoveEmptyEntries));
var sb = new StringBuilder();

foreach (string item in lbxCodes.Items.Cast<string>())
{
    if (resultElements.Contains(item))
    {
        if (sb.Length > 0)
            sb.Append(',');
        sb.Append(item);
    }
}

return sb.ToString();

场景2：待匹配项是长字符串中的任意子串 #

如果项可能是Result里的任意子串（比如"abc"出现在"xyzabc123"中），用Aho-Corasick多模式匹配算法可以一次性完成所有模式的匹配，时间复杂度降到O(M + N + K)（M是长字符串长度，N是所有项的总长度，K是匹配结果数），效率远高于逐个调用Contains。

这里提供一个简化版的Aho-Corasick实现，结合StringBuilder使用：

// 简化版Aho-Corasick多模式匹配类
public class AhoCorasickMatcher
{
    private class Node
    {
        public Dictionary<char, Node> Children { get; } = new();
        public Node Fail { get; set; }
        public List<string> Matches { get; } = new();
    }

    private readonly Node _root;

    public AhoCorasickMatcher(IEnumerable<string> patterns)
    {
        _root = new Node();
        // 构建字典树
        foreach (var pattern in patterns)
        {
            var current = _root;
            foreach (var c in pattern)
            {
                if (!current.Children.TryGetValue(c, out var child))
                {
                    child = new Node();
                    current.Children[c] = child;
                }
                current = child;
            }
            current.Matches.Add(pattern);
        }
        // 构建失败指针
        var queue = new Queue<Node>();
        foreach (var child in _root.Children.Values)
        {
            child.Fail = _root;
            queue.Enqueue(child);
        }
        while (queue.Count > 0)
        {
            var current = queue.Dequeue();
            foreach (var (c, child) in current.Children)
            {
                var failNode = current.Fail;
                while (failNode != null && !failNode.Children.ContainsKey(c))
                    failNode = failNode.Fail;
                child.Fail = failNode?.Children.GetValueOrDefault(c) ?? _root;
                child.Matches.AddRange(child.Fail.Matches);
                queue.Enqueue(child);
            }
        }
    }

    public HashSet<string> FindAllMatches(string text)
    {
        var matches = new HashSet<string>();
        var current = _root;
        foreach (var c in text)
        {
            while (current != null && !current.Children.ContainsKey(c))
                current = current.Fail;
            current = current?.Children.GetValueOrDefault(c) ?? _root;
            foreach (var match in current.Matches)
                matches.Add(match);
        }
        return matches;
    }
}

// 使用示例
var allItems = lbxCodes.Items.Cast<string>();
var matcher = new AhoCorasickMatcher(allItems);
var matchedItems = matcher.FindAllMatches(Result);

var sb = new StringBuilder();
foreach (var item in matchedItems)
{
    if (sb.Length > 0)
        sb.Append(',');
    sb.Append(item);
}

return sb.ToString();

额外提示 #

• 不管哪种场景，都要用lbxCodes.Items.Cast<string>()避免装箱拆箱的性能开销，20万项的情况下这个优化很有必要。
• 如果用.NET Core/.NET 5+，也可以尝试把所有项转成正则表达式（用|分隔），但要注意转义特殊字符，且20万项的正则表达式可能会过长，性能不如Aho-Corasick稳定。

内容的提问来源于stack exchange，提问作者asmgx