当前位置:

首页 > 编程开发 > C++实现KMP算法查找子串索引详解

C++实现KMP算法查找子串索引详解

KMP的价值在于最坏时间复杂度严格为O(n+m),适用于需确定性延迟的场景;computeLPS须设lps[0]=0并正确回退;主循环中j和i更新需避免死循环与漏匹配;实际项目通常无需手写,C++20std::search更优;KMP不支持UTF-8,需转u32string或用ICU。

本文目录

    KMP的价值在于最坏时间复杂度严格为O(n+m),适用于需确定性延迟的场景;computeLPS须设lps[0]=0并正确回退;主循环中j和i更新需避免死循环与漏匹配;实际项目通常无需手写,C++20 std::search更优;KMP不支持UTF-8,需转u32string或用ICU。

    c++中如何实现KMP字符串匹配_c++高效查找子串索引算法【详解】

    为什么不能直接用 std::string::find 就完事?

    多数场景下,std::string::find 确实够用,它底层通常已做优化(如混合 BM / Sunday 启发式),平均性能不差。但 KMP 的价值不在“更快”,而在「最坏时间复杂度严格为 O(n + m)」——当你必须保证线性、且输入模式串(pattern)可能高度退化(比如全是 'a')、文本串(text)也恶意构造时,朴素匹配会退化到 O(n×m),而 KMP 不会。

    典型触发场景:编译器词法分析预处理、网络包深度检测(DPI)、嵌入式资源受限环境需确定性响应延迟。

    computeLPS 函数怎么写才不出错?

    LPS(Longest Proper Prefix which is also Suffix)数组是 KMP 的核心预处理结果。常见错误是边界判断混乱、指针/索引混用、或忽略 lps[0] == 0 的强制约定。

    • 起始必须设 lps[0] = 0,因为长度为 1 的子串没有 proper prefix
    • 主循环从 i = 1 开始,用 len 表示当前已匹配的前缀长度(也是上一个位置的 lps 值)
    • 当 pattern[i] != pattern[len] 且 len > 0 时,要回退:len = lps[len - 1];不能写成 len-- 或 len = lps[len]
    • 匹配成功后,lps[i] = ++len,注意是先自增再赋值
    void computeLPS(const std::string& pattern, std::vector& lps) {
        lps[0] = 0;
        int len = 0;
        size_t i = 1;
        while (i < pattern.length()) {
            if (pattern[i] == pattern[len]) {
                lps[i] = ++len;
                ++i;
            } else {
                if (len != 0) {
                    len = lps[len - 1]; // 关键:不是 len--
                } else {
                    lps[i] = 0;
                    ++i;
                }
            }
        }
    }

    主匹配循环里 j 和 i 的更新逻辑为何总出 bug?

    变量命名混乱是高频坑:i 是 text 指针,j 是 pattern 指针。常见错误包括:

    • 匹配成功后只写 j++ 却忘了 i++(导致死循环)
    • 失配时只改 j 却没动 i(正确做法是仅 j = lps[j-1],i 不回退)
    • 找到一个匹配后未重置 j 就继续找下一个(应设 j = lps[j-1] 而非归零,否则漏掉重叠匹配,如在 "aaaa" 中找 "aa" 应返回索引 0 和 1)
    std::vector kmpSearch(const std::string& text, const std::string& pattern) {
        if (pattern.empty()) return {};
        std::vector lps(pattern.length());
        computeLPS(pattern, lps);
    
    std::vector result;
    size_t i = 0, j = 0;
    while (i < text.length()) {
        if (pattern[j] == text[i]) {
            ++i;
            ++j;
        }
        if (j == pattern.length()) {
            result.push_back(i - j);
            j = lps[j - 1]; // 注意:这里不是 j = 0
        } else if (i < text.length() && pattern[j] != text[i]) {
            if (j != 0) j = lps[j - 1];
            else ++i;
        }
    }
    return result;

    }

    实际项目中要不要手写 KMP?

    绝大多数 C++ 工程无需手写。C++20 引入了 std::search 配合 std::default_searcher(基于 Boyer-Moore),性能通常优于手写 KMP;若需 C++17 及更早版本,absl::string_view::find(来自 Abseil)或 boost::algorithm::find_all 更可靠。

    真正需要手写 KMP 的情况极少:比如你正在实现一个轻量级脚本引擎,不允许链接第三方库,又必须支持超长日志行中查找重复指令序列,且对 worst-case 延迟有硬性要求——这时才值得把上面两个函数抠出来,加上 constexpr 支持和 char8_t 适配。

    最容易被忽略的一点:KMP 对 Unicode(UTF-8)字符串无效。它按字节操作,而 UTF-8 中一个字符占 1–4 字节。真要处理中文等,必须先转为 std::u32string 或用 ICU 库做正规化。

    本站声明:本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系bd@zhengruan.com
    作者最新文章
    编程开发
    相关文章 更多
    Ducter 0.0.56继续手机任务时工具怎样恢复,回复语言为何不再错位
    Ducter 0.0.56继续手机任务时工具怎样恢复,回复语言为何不再错位

    Ducter 0.0.56修复已结束手机任务续跑时的工具缺失,并避免点击其他Agent请求卡片后回复语言错位。

    Plannotator 0.28.65的账号限制和Inbox存储变化怎样理解
    Plannotator 0.28.65的账号限制和Inbox存储变化怎样理解

    Plannotator 0.28.65收紧Tailscale所有者账号访问、迁回文件存储,Take back只适用于尚未交付回复。

    WorkBuddy怎么用API接口?有开发文档吗
    WorkBuddy怎么用API接口?有开发文档吗

    WorkBuddy 目前没有面向普通用户的公开 REST API 接口文档,扩展与集成走四条官方路径:接入 MCP 服务扩展工具能力、用连接器打通外部应用(支持公共/个人授权)、编写技能(Skill)与专家包定制工作流、在开放平台发布 Buddy 应用。另支持接入 OpenAI 兼容的自定义模型。本文含 4 张真实界面截图并如实说明现状。

    Google Workspace MCP OAuth 2.0迁移节点已过,旧客户端、普通REST与服务账户分别适用什么规则
    Google Workspace MCP OAuth 2.0迁移节点已过,旧客户端、普通REST与服务账户分别适用什么规则

    解释Google Workspace MCP 11月11日与12日的agentic OAuth客户端迁移节点,区分普通REST应用、混合客户端、预览资格、用户权限和服务账户、Apps Script边界。

    OpenAI Agents SDK v0.24.0-alpha.8升级前为何要备份状态?
    OpenAI Agents SDK v0.24.0-alpha.8升级前为何要备份状态?

    OpenAI Agents SDK v0.24.0-alpha.8预览版新增执行前审批、自有模型客户端、Realtime与预算检查点恢复,说明alpha.7回退、Linux运行及工具认证边界。

    Claude Trading Skills六项诊断修复覆盖哪些密钥泄漏路径?
    Claude Trading Skills六项诊断修复覆盖哪些密钥泄漏路径?

    Claude Trading Skills六项技能已修复API密钥异常日志泄漏路径;not_verified保留完整安全审核缺口,离线回归通过不等于实盘验收或全面认证。

    Microsoft C++ Language Server内置MSBuild提取器后,自动化范围和使用资格怎样理解
    Microsoft C++ Language Server内置MSBuild提取器后,自动化范围和使用资格怎样理解

    解释Microsoft C++ Language Server预览版的MSBuild编译数据库自动提取,区分CMake、自定义构建、有效Copilot订阅和CLI能力,避免把测试预发布版本当最低稳定版。

    LibreOffice宏怎么用?Python脚本能调用吗
    LibreOffice宏怎么用?Python脚本能调用吗

    LibreOffice可通过“工具→宏”创建和运行Basic宏,也支持由Python脚本提供程序运行Python宏。两种方式都可以使用UNO接口操作文档;Excel VBA只有有限兼容支持,不能把所有Excel宏直接复制过来当作LibreOffice原生宏执行。

    GitHub企业Copilot席位API开放应用调用后,读取和席位变更有什么区别
    GitHub企业Copilot席位API开放应用调用后,读取和席位变更有什么区别

    说明Enterprise GitHub Apps的Copilot席位管理权限,提供第一页只读GET示例,区分total_seats、授权明细、遥测活动和待取消计费条件。

    GitHub网页仪表盘默认视图、单行标题和六项列表分别改变什么
    GitHub网页仪表盘默认视图、单行标题和六项列表分别改变什么

    解释GitHub网页仪表盘Feed或Home默认视图、六项列表、自定义选择保留和Agent sessions隐藏条件,区分布局、数据与权限。

    查看更多
    精品专题 更多
    装机必备
    装机必备

    正软商城装机必备专区,精选办公、浏览器、安全防护、影音播放、压缩解压、设计创作和系统工具等电脑常用正版软件,帮助用户快速完成新电脑软件配置。

    Windows
    Windows

    正软商城Windows软件专区,汇集适用于Windows电脑的办公、设计、安全防护、影音播放、开发工具和系统优化软件,提供软件介绍、系统要求、正版授权及购买下载服务。

    PDF教程
    PDF教程

    正软商城PDF教程频道提供PDF编辑、转换、合并、拆分、压缩及格式处理方法,同时介绍常用PDF软件和工具的使用技巧。

    Mac软件 更多
    讯飞智作 网页版
    讯飞智作 网页版
    Windows/ macOS/ Linux

    讯飞智作是一款基于语音合成技术、虚拟人驱动技术与数字人形象声音构建能力的 AI 数字人音视频创作平台。

    火山引擎 网页版
    火山引擎 网页版
    Windows/ macOS/ Linux

    火山引擎是字节跳动旗下企业级云与AI服务平台。聚焦大模型核心能力,依托字节自研豆包多模态大模型,凭借火山方舟一站式平台,提供模型精调、推理部署、智能应用搭建等全链路服务,结合高性能AI算力,助力各行业快速落地大模型数字化与智能化应用。

    Aperty macOS版
    Aperty macOS版
    macOS

    Aperty 是 Skylum 推出的 AI 人像修图软件,支持自然肤质修饰、瑕疵处理、面部与身体调整、预设及批量同步。

    WINDOWS 更多
    讯飞智作 网页版
    讯飞智作 网页版
    Windows/ macOS/ Linux

    讯飞智作是一款基于语音合成技术、虚拟人驱动技术与数字人形象声音构建能力的 AI 数字人音视频创作平台。

    火山引擎 网页版
    火山引擎 网页版
    Windows/ macOS/ Linux

    火山引擎是字节跳动旗下企业级云与AI服务平台。聚焦大模型核心能力,依托字节自研豆包多模态大模型,凭借火山方舟一站式平台,提供模型精调、推理部署、智能应用搭建等全链路服务,结合高性能AI算力,助力各行业快速落地大模型数字化与智能化应用。

    PixTV 网页版
    PixTV 网页版
    Windows

    PixTV 是一款在浏览器中使用的 AI 视觉内容创作平台,提供图片、视频、音频、文字生成、AI 分镜、局部重绘、提示词反推和无限画布等工具,适合短剧、漫剧、广告及社交媒体内容制作。