C++ 中的子串搜索：从朴素到高性能

前言：为什么“直接用 find()”不总是答案

想象一下这个场景：你正在编写一个日志解析器，每秒处理数百万行日志，或者一个文本搜索引擎。你首先想到的可能是调用 std::string::find()。“能用吗？能用。还需要什么？”——90% 的程序员都会这么想。他们是对的……直到某个时刻，10 毫秒的差距决定了整个应用的命运。

在 Stack Overflow 上，“Check if a string contains a string in C++”这个问题获得了数十万次浏览。这并非偶然。这个看似简单的任务隐藏着许多陷阱：从搜索算法的选择，到如何正确使用 C++17 和 C++20 的现代特性。

在本文中，我们不仅会展示如何检查字符串是否包含子串。我们将深入探讨 7 种实现方法，在真实数据上比较它们的性能，并为不同场景提供明确的建议。开始吧！

经典之作：std::string::find()

我们从每个人都知道的基础开始。find() 方法返回子串第一次出现的位置，如果未找到则返回特殊值 std::string::npos。

#include <iostream>\n#include <string>\n\nint main() {\n    std::string haystack = "Hello, C++ developer!";\n    std::string needle = "C++";\n    \n    if (haystack.find(needle) != std::string::npos) {\n        std::cout << "子串已找到！" << std::endl;\n    }\n    \n    // 指定起始位置进行搜索\n    size_t pos = haystack.find("C++", 5); // 从第 5 个字符开始\n    return 0;\n}

优点：简单、可读性强、内置于 STL。
\n缺点：使用朴素搜索算法（最坏情况下 O(n*m)）。对于短字符串来说很理想，但对于长字符串可能会变慢。

何时 find() 是“罪魁祸首”？

如果你在长度超过 10⁵ 个字符的字符串中搜索子串，且子串较长且重复（例如，在 "aaaaaaaaaaaaaaaaaaaaab" 中搜索 "aaaaaab"），朴素算法性能会开始下降。在这种情况下，find() 可能比优化后的替代方案慢 10 到 100 倍。

string_view：轻量与高速

随着 C++17 的到来，我们有了 std::string_view——一种非拥有型的字符串视图。它非常适合那些只读取数据而不复制数据的函数。

#include <iostream>\n#include <string_view>\n\nbool contains(std::string_view haystack, std::string_view needle) {\n    return haystack.find(needle) != std::string_view::npos;\n}\n\nint main() {\n    std::string_view text = "C++ 中的优化是一门艺术";\n    std::string_view pattern = "艺术";\n    \n    if (contains(text, pattern)) {\n        std::cout << "已找到！" << std::endl;\n    }\n    return 0;\n}

为什么更快？ 当传递 std::string 给函数时，会发生复制（除非通过引用传递）。string_view 只复制指针和长度——没有内存分配。对于频繁的包含检查调用，这可以带来高达 30-40% 的性能提升。

算法升级：Boyer-Moore 和 KMP

如果你处理的是真正的大数据，是时候回顾经典的子串搜索算法了。在 C++17 中，出现了 STL 搜索算法：

\n
• std::boyer_moore_searcher —— 对于长模式来说最快的算法之一
\n
• std::boyer_moore_horspool_searcher —— 简化版本，在短模式上更快
\n
• std::default_searcher —— 朴素搜索的包装器
\n

#include <iostream>\n#include <string>\n#include <algorithm>\n#include <functional>\n\nint main() {\n    std::string text = "C++ 中的搜索算法可以非常快";\n