C#中快速判断字符串是否包含列表所有元素的最优方案

针对你遇到的问题——需要快速验证数百个短语（含多词短语）是否全部存在于数千万字符级的超大字符串中，原方案的核心问题是每个短语单独调用string.Contains都会遍历整个大字符串，时间复杂度为O(N*M)（N是短语数，M是字符串长度），重复开销极大。以下是几种更高效的优化方案：

方案一：短语HashSet预构建（推荐，实现简单高效） #

如果你的短语最大单词数不大（比如≤5），这个方法能大幅降低时间复杂度：通过拆分超大字符串为单词列表，预先生成所有可能的连续短语存入HashSet，之后只需O(1)查询每个短语是否存在。

代码示例 #

List<string> uniqueWords = new List<string> { "two", "three", "weather sunday" };
string final = "two and tomorrow\n\rtwo or wednesday\n\rtwo with thursday\n\rtwo without friday\n\rthree gone tomorrow\n\rthree weather saturday\n\rthree timely sunday";

// 1. 定义单词分隔符（根据实际场景调整，比如加上逗号、分号等）
var wordSeparators = new[] {' ', '\n', '\r', '\t'};

// 2. 拆分超大字符串为单词列表
var finalWords = final.Split(wordSeparators, StringSplitOptions.RemoveEmptyEntries);

// 3. 统计原列表中短语的最大单词数，减少不必要的短语生成
int maxWordCount = uniqueWords.Max(item => item.Split(wordSeparators, StringSplitOptions.RemoveEmptyEntries).Length);

// 4. 预构建所有可能的连续短语HashSet（支持忽略大小写）
HashSet<string> existingPhrases = new HashSet<string>(StringComparer.CurrentCultureIgnoreCase);
for (int i = 0; i < finalWords.Length; i++)
{
    StringBuilder sb = new StringBuilder();
    // 生成从当前单词开始，长度1到maxWordCount的连续短语
    for (int len = 1; len <= maxWordCount && i + len <= finalWords.Length; len++)
    {
        if (len > 1)
            sb.Append(' ');
        sb.Append(finalWords[i + len - 1]);
        existingPhrases.Add(sb.ToString());
    }
}

// 5. 快速检查所有短语是否存在，收集缺失项
var missingItems = uniqueWords.Where(item => !existingPhrases.Contains(item)).ToList();

// 输出结果：这里会得到["weather sunday"]
foreach (var item in missingItems)
{
    Console.WriteLine($"缺失短语：{item}");
}

优势 #

• 实现简单，无需复杂算法
• 时间复杂度降至O(WL + N)（W是单词数，L是最大短语长度，N是原列表元素数），远低于原方案的O(NM)
• 查询阶段是O(1)哈希查找，速度极快

方案二：Aho-Corasick多模式匹配算法（适合超大量短语场景） #

如果你的短语数量极多（比如上千个）或短语长度差异极大，Aho-Corasick算法是最优选择：它只需遍历一次超大字符串，就能同时匹配所有目标短语，时间复杂度为O(M + K)（M是字符串长度，K是所有短语的总字符数）。

代码示例（简化版AC自动机实现） #

public class AcNode
{
    public Dictionary<char, AcNode> Children { get; } = new Dictionary<char, AcNode>();
    public AcNode Fail { get; set; }
    public HashSet<string> MatchedPhrases { get; } = new HashSet<string>();
}

public class AcAutomaton
{
    private readonly AcNode _root = new AcNode();

    public void AddPattern(string pattern)
    {
        var current = _root;
        foreach (char c in pattern)
        {
            if (!current.Children.TryGetValue(c, out var child))
            {
                child = new AcNode();
                current.Children[c] = child;
            }
            current = child;
        }
        current.MatchedPhrases.Add(pattern);
    }

    public void BuildFailLinks()
    {
        Queue<AcNode> queue = new Queue<AcNode>();
        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.MatchedPhrases.UnionWith(child.Fail.MatchedPhrases);
                queue.Enqueue(child);
            }
        }
    }

    public HashSet<string> FindAllMatches(string text, StringComparison comparison = StringComparison.Ordinal)
    {
        HashSet<string> matches = new HashSet<string>();
        var current = _root;
        foreach (char c in text)
        {
            char targetC = comparison == StringComparison.OrdinalIgnoreCase ? char.ToLowerInvariant(c) : c;
            while (current != null && !current.Children.ContainsKey(targetC))
            {
                current = current.Fail;
            }
            current = current?.Children.GetValueOrDefault(targetC) ?? _root;
            foreach (var phrase in current.MatchedPhrases)
            {
                matches.Add(phrase);
            }
        }
        return matches;
    }
}

// 使用示例
var automaton = new AcAutomaton();
foreach (var phrase in uniqueWords)
{
    // 忽略大小写的话，统一转小写存入（或在匹配时处理）
    automaton.AddPattern(phrase.ToLowerInvariant());
}
automaton.BuildFailLinks();

// 匹配超大字符串
var matchedPhrases = automaton.FindAllMatches(final.ToLowerInvariant());

// 收集缺失项
var missingItems = uniqueWords.Where(item => !matchedPhrases.Contains(item.ToLowerInvariant())).ToList();

优势 #

• 最优时间复杂度，适合超大量短语或超长字符串场景
• 只需遍历一次超大字符串，避免重复扫描

方案三：ReadOnlySpan常数项优化（快速改进原方案） #

如果不想改动太大，可通过ReadOnlySpan<char>优化原方案的Contains操作，减少字符串拷贝开销，性能比原生string.Contains提升约20%-30%：

ReadOnlySpan<char> finalSpan = final.AsSpan();
var missingItems = uniqueWords.Where(item => !finalSpan.Contains(item.AsSpan(), StringComparison.CurrentCultureIgnoreCase)).ToList();

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