讲师中心 微信公众号

工具推荐

视频效率加速
Laper
Laper

剧本策划到成片协作

updream

一键生成高质量推广成片

Seko
Seko

AI短剧一键生成成片

AniShort
AniShort

AI短剧协同制作平台

c++中如何实现字符串的kmp算法_c++ KMP模式匹配详解

酷伟吖_1520

酷伟吖_1520

发布时间:2026-01-02 15:58:02

|

956人浏览过

|

来源于php中文网

原创

next数组表示模式串各前缀的最长真公共前后缀长度,用于KMP算法中实现主串指针不回退;因std::string::find不暴露中间状态且底层不保证KMP,故需手写build_next函数,注意next[0]=0、双指针正确更新及边界处理。

c++中如何实现字符串的kmp算法_c++ kmp模式匹配详解

什么是 next 数组,为什么不能直接用 std::string::find

因为 std::string::find 底层不保证是 KMP,且无法获取匹配过程中的中间状态(比如每次失配跳转位置),而 KMP 的核心价值恰恰在于 next 数组驱动的「不回退主串指针」行为。它适用于流式处理、自定义匹配逻辑或教学分析场景。

next[i] 表示模式串 pattern[0..i] 的最长真前缀同时也是后缀的长度。注意:不同教材对 next 定义略有差异——有的存的是「最大公共前后缀长度减 1」,有的存「下一次应比较的位置索引」。C++ 实现中建议统一用「长度版」,避免负索引和边界混淆。

  • 若 pattern = "ababaca",则 next = [0,0,0,1,2,3,0]
  • 构建时用双指针:j 指向当前待求位置,i 指向前缀末尾;当 pattern[i] == pattern[j] 时,next[j++] = i + 1
  • 失配时,i 不回退主串位置,而是根据 next[i-1] 跳转模式串位置

如何手写 build_next 函数避免越界和逻辑错位

常见错误是把 next[0] 设为 -1 或未初始化,导致后续 i 变成负数;或者在构建循环里误用 i 导致死循环。正确做法是让 <code>next[0] = 0,并用 i = 0 作为前缀长度计数器。

std::vector<int> build_next(const std::string& pattern) {
    if (pattern.empty()) return {};
    std::vector<int> next(pattern.size(), 0);
    int i = 0; // 当前匹配的前缀长度
    for (int j = 1; j < pattern.size(); ++j) {
        while (i > 0 && pattern[i] != pattern[j]) {
            i = next[i - 1];
        }
        if (pattern[i] == pattern[j]) {
            ++i;
        }
        next[j] = i;
    }
    return next;
}

KMP 主匹配循环里怎么控制 i 和 j 不越界

主串索引 i 必须严格递增(这是 KMP 高效的关键),模式串索引 j 在失配时靠 next 回跳。最容易漏掉的判断是:当 j == pattern.size() 时,说明完成一次匹配,此时要先记录位置,再令 j = next[j - 1] 继续找重叠匹配(如 pattern="aa" 在 "aaaa" 中应匹配三次)。

C++14
C++14

C++14 对 C++11 的修正与增强版本,适合旧系统维护和较老工具链兼容。

下载

立即学习“C++免费学习笔记(深入)”;

  • 主循环条件是 i ,不是 <code>i
  • 每次成功匹配字符后必须 ++i; ++j;,否则会重复比较或卡死
  • 当 j == 0 && text[i] != pattern[0] 时,只能 ++i,不能尝试 next[-1]

为什么 C++ 中用 std::vector<int></int> 而不用 int* 手动管理内存

现代 C++ 已无需手动 new/delete。用 std::vector 可避免栈溢出(长模式串导致大数组)、释放遗漏、以及跨函数生命周期问题。尤其当 pattern 是临时对象时,返回 vector 是安全的(C++11 后有移动语义优化)。

如果硬要优化空间(比如嵌入式环境),可将 next 数组复用为局部栈数组,但前提是已知最大模式长度;否则仍推荐 vector ——它的 capacity() 增长策略比手写扩容更可靠,且不会因 realloc 失败而崩溃。

真正容易被忽略的是:KMP 的「线性时间」只在 next 构建和主匹配都完成的前提下成立;如果频繁构造 next(比如每次匹配都重新算),整体就退化为 O(n×m)。实际使用中,应缓存 next 数组,尤其当同一个模式串要匹配多个主串时。

相关文章

c++速学教程(入门到精通)
c++速学教程(入门到精通)

c++怎么学习?c++怎么入门?c++在哪学?c++怎么学才快?不用担心,这里为大家提供了c++速学教程(入门到精通),有需要的小伙伴保存下载就能学习啦!

下载

相关标签:

c++

本站声明:本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系admin@php.cn

热门AI工具

更多
SkildArt
SkildArt Hot

SkildArt是一款AI文本写作工具,一站式 AI 视觉创作平台。

切问学术

切问学术是一款AI论文写作工具,复旦大学NLP团队推出的AI学术智能体。

小橡皮AI

一款AI工具,主要用于小橡皮一键去AI味,将机器味重的内容改得更有活人感,防止因为 AI 内容被平台打上 AI 标签,以及限流,适合需要提升相关任务效率的用户。

PixPix
PixPix Hot

PixPix是一款面向电商视觉生产的AI商品图生成工具。

WorkBuddy

一款AI办公效率工具,主要用于腾讯云推出的AI原生桌面智能体工作台,适合需要提升相关任务效率的用户。

DeepSeek

DeepSeek是一款面向对话、写作、编程和推理场景的AI大模型工具。

豆包大模型

豆包大模型是一款由字节跳动推出的企业级大语言模型服务平台。

讯飞绘文

讯飞绘文是一款由科大讯飞推出的一站式 AIGC 内容运营平台。

码上飞
码上飞 Hot

一款基于自然语言的AI应用开发平台,可根据用户描述自动生成应用程序,帮助个人和团队快速完成应用原型与开发。

相关专题

更多
string转int
string转int

在编程中,我们经常会遇到需要将字符串(str)转换为整数(int)的情况。这可能是因为我们需要对字符串进行数值计算,或者需要将用户输入的字符串转换为整数进行处理。php中文网给大家带来了相关的教程以及文章,欢迎大家前来学习阅读。

7679

2023.08.02

js 字符串转数组
js 字符串转数组

js字符串转数组的方法:1、使用“split()”方法;2、使用“Array.from()”方法;3、使用for循环遍历;4、使用“Array.split()”方法。本专题为大家提供js字符串转数组的相关的文章、下载、课程内容,供大家免费下载体验。

1958

2023.08.03

js截取字符串的方法
js截取字符串的方法

js截取字符串的方法有substring()方法、substr()方法、slice()方法、split()方法和slice()方法。本专题为大家提供字符串相关的文章、下载、课程内容,供大家免费下载体验。

3264

2023.09.04

java基础知识汇总
java基础知识汇总

java基础知识有Java的历史和特点、Java的开发环境、Java的基本数据类型、变量和常量、运算符和表达式、控制语句、数组和字符串等等知识点。想要知道更多关于java基础知识的朋友,请阅读本专题下面的的有关文章,欢迎大家来php中文网学习。

6444

2023.10.24

字符串介绍
字符串介绍

字符串是一种数据类型,它可以是任何文本,包括字母、数字、符号等。字符串可以由不同的字符组成,例如空格、标点符号、数字等。在编程中,字符串通常用引号括起来,如单引号、双引号或反引号。想了解更多字符串的相关内容,可以阅读本专题下面的文章。

6669

2023.11.24

java读取文件转成字符串的方法
java读取文件转成字符串的方法

Java8引入了新的文件I/O API,使用java.nio.file.Files类读取文件内容更加方便。对于较旧版本的Java,可以使用java.io.FileReader和java.io.BufferedReader来读取文件。在这些方法中,你需要将文件路径替换为你的实际文件路径,并且可能需要处理可能的IOException异常。想了解更多java的相关内容,可以阅读本专题下面的文章。

8194

2024.03.22

php中定义字符串的方式
php中定义字符串的方式

php中定义字符串的方式:单引号;双引号;heredoc语法等等。想了解更多字符串的相关内容,可以阅读本专题下面的文章。

12814

2024.04.29

go语言字符串相关教程
go语言字符串相关教程

本专题整合了go语言字符串相关教程,阅读专题下面的文章了解更多详细内容。

6679

2025.07.29

Go-Zero API开发使用教程
Go-Zero API开发使用教程

本专题聚焦Go-Zero的API开发,拆解.api描述文件的语法结构、路由与分组定义、参数绑定与校验规则,说明统一响应体、JWT鉴权、跨域与接口文档生成的落地方式,并给出网关聚合与接口测试的实践建议。

140

2026.11.12

热门下载

更多
网站特效
/
网站源码
/
网站素材
/
前端模板

精品课程

更多
相关推荐
/
热门推荐
/
最新课程
C++ Core Guidelines
C++ Core Guidelines

共0课时 | 0人学习

C++ Reference
C++ Reference

共0课时 | 0人学习

C++ 官方标准说明
C++ 官方标准说明

共0课时 | 0人学习

关于我们 免责申明 举报中心 意见反馈 讲师合作 广告合作 最新更新
php中文网:公益在线php培训,帮助PHP学习者快速成长!
关注服务号
PHP中文网订阅号
每天精选资源文章推送

Copyright 2014-2026 https://www.php.cn/ All Rights Reserved | php.cn