当前位置：首页 > news >正文

串的KMP算法详解

news 来源：原创 2025/8/16 6:00:02

KMP算法深度解析

一、从暴力匹配到智能跳转：

在文本编辑器的搜索功能中，当我们在百万字的文档中查找特定关键词时，传统暴力匹配算法的时间复杂度高达O(mn)。KMP算法通过独创的部分匹配表（Partial Match Table），将时间复杂度降为线性的O(m+n)，性能提升可达1000倍！
KMP算法的核心思路是通过预处理模式串，构建一个部分匹配表（Partial Match Table，简称PMT），也称为最长前缀后缀数组（Longest Prefix Suffix，简称LPS）。这个表用于在匹配过程中，当出现不匹配的情况时，能够快速确定模式串的下一个匹配位置，从而避免不必要的回溯比较。
为此定义了next[j]函数，表明当模式中第j个字符与主串中的相应字符“失配“时，在模式中需要重新和主串中该字符进行比较的字符的位置
利用部分匹配的结果加快模式快的滑动速度，且主串的指针i不必回溯，可提速到O(n+m)

经典场景对比

void bf(char* text, char* pattern) {int textlen = strlen(text);int patternlen = strlen(pattern);int i = 0, j = 0;while (i <= textlen  && j < patternlen) {if (text[i] == pattern[j]) {i++; j++;}else {i = i - j + 1;        //回溯到最开始匹配的下一位j = 0;                //重新开始}}if (j == patternlen) {printf("匹配到的位置为：%d\n", i - patternlen + 1);}else {printf("匹配失败");}
}

二、KMP核心机制：部分匹配表的精妙设计

2.1 最长公共前后缀（LPS）计算

给定模式串"ABABCABAB"，其部分匹配表构建过程如下：

索引	0	1	2	3	4	5	6	7	8
字符	A	B	A	B	C	A	B	A	B
next	0	0	1	2	0	1	2	3	4

构建原理：
对于每个位置i，找到最长的k使得pattern[0:k] == pattern[i-k:i]

2.2 next数组生成算法

void get_next(SString s, int *next) {int i = 1, k = 0;next[1] = 0;while (i < s.length) {if (k == 0 || s.ch[i] == s.ch[k]) {++i;++k;next[i] = k;} else {k = next[k];}}
}

三、KMP算法实现详解

3.1 匹配过程可视化

void kmp(SString text, SString pattern) {int textlen = text.length;int patternlen = pattern.length;int i = 1, j = 1;int next[Maxsize];  // 确保 next 数组的大小为 Maxsizeget_next(pattern, next);while (i <= textlen && j <= patternlen) {if (j == 0 || text.ch[i] == pattern.ch[j]) {i++;j++;} else {j = next[j];}}if (j > patternlen) {printf("匹配到的位置为：%d\n", i - patternlen);} else {printf("匹配失败\n");}
}

3.2 复杂度分析

时间复杂度：O(m+n)
预处理O(m)，匹配过程O(n)
空间复杂度：O(m)
存储next数组

四、KMP的优化演进

4.1 Next数组优化版

void get_nextval(SString s, int *nextval) {int i = 1, k = 0;nextval[1] = 0;while (i < s.length) {if (k == 0 || s.ch[i] == s.ch[k]) {++i;++k;if(s.ch[i]!=s.ch[k])nextval[i]=k;elsenextval[i]=nextval[k];} else {k = nextval[k];}}
}

4.2 应用场景对比

算法	最佳场景	最差时间复杂度	预处理成本
Brute-Force	短模式串	O(mn)	无
KMP	重复模式	O(m+n)	O(m)
Boyer-Moore	英文文本	O(mn)	O(m+σ)
Sunday	字符集较大	O(mn)	O(m+σ)

工业级应用案例

生物信息学的DNA序列匹配

人类基因组包含约30亿个碱基对，KMP算法在基因序列比对中表现出色：

# DNA序列匹配示例
dna_sequence = "ATCGATCGATCGATCG..."
gene_pattern = "ATCGATCGA"
position = kmp_search(dna_sequence, gene_pattern)

敏感词过滤系统

某社交平台使用KMP实现毫秒级敏感词检测：

实现原理：通过与敏感关键字库一一比较

思维革命

KMP算法不仅仅是一个高效的字符串匹配工具，其核心思想——利用已知信息避免重复计算，在动态规划、编译原理等领域都有广泛应用。建议读者：

手写实现next数组构建过程
在LeetCode上练习相关题目（如Implement strStr()）
研究KMP在正则表达式引擎中的应用

真正理解KMP的精髓，将使您在解决复杂算法问题时获得全新的视角。下一次当您使用Ctrl+F搜索时，不妨想想这个改变计算机历史的伟大算法！

串的KMP算法详解

KMP算法深度解析一、从暴力匹配到智能跳转： 在文本编辑器的搜索功能中，当我们在百万字的文档中查找特定关键词时，传统暴力匹配算法的时间复杂度高达O(mn)。KMP算法通过独创的部分匹配表（Partial Match Table）&#x…...

编程日记 2025/8/16 6:00:02

软件测试之测试分类

1. 为什么要对软件测试进行分类软件测试是软件⽣命周期中的⼀个重要环节，具有较⾼的复杂性，对于软件测试，可以从不同的⻆度加以分类，使开发者在软件开发过程中的不同层次、不同阶段对测试⼯作进⾏更好的执⾏和管理测试的分类⽅…...

编程日记 2025/8/16 5:57:53

机器学习 : 训练过程

文章目录概要流程1 . 前向传播2 . 计算损失3 . 后向传播4 . 梯度下降技术名词解释小结【全文大纲】 : https://blog.csdn.net/Engineer_LU/article/details/135149485 概要主要思想拟合数据流程 1 . 前向传播 y func * (wxb) 2 . 计算损失 y - Y 3 . 后向传播根据链式法…...

编程日记 2025/8/15 17:58:02

六十天前端强化训练之第二十天React Router 基础详解

欢迎来到编程星辰海的博客讲解看完可以给一个免费的三连吗，谢谢大佬！ 目录一、核心概念 1.1 核心组件 1.2 路由模式对比二、核心代码示例 2.1 基础路由配置 2.2 动态路由示例 2.3 嵌套路由实现 2.4 完整示例代码三、关键功能实现效果四、…...

编程日记 2025/8/16 5:57:42

如何在AVL树中高效插入并保持平衡：一步步掌握旋转与平衡因子 —— 旋转篇

文章目录 AVL树种旋转的规则右单旋右单旋代码左单旋左单旋代码左右双旋左右单旋的代码右左单旋右左单旋的代码 AVL树种旋转的规则在AVL树中，旋转是为了保持树的平衡性。AVL树是一种自平衡的二叉搜索树，它要求每个节点的左右子树的高度差不能超过1。当插…...

编程日记 2025/8/16 5:58:18

C++Primer学习（7.1 定义抽象数据类型）

类的基本思想是数据抽象(data abstraction)和封装(encapsulation)。数据抽象是种依赖于接口(interface)和实现(implementation)分离的编程(以及设计)技术。类的接口包括用户所能执行的操作:类的实现则包括类的数据成员、负责接口实现的函数体以及定义类所需的各种私有函数。封…...

编程日记 2025/8/16 5:56:25

Vue 3 Diff 算法深度解析：与 Vue 2 双端比对对比

文章目录 1. 核心算法概述1.1 Vue 2 双端比对算法1.2 Vue 3 快速 Diff 算法 2. 算法复杂度分析2.1 时间复杂度对比2.2 空间复杂度对比 3. 核心实现解析3.1 Vue 2 双端比对代码3.2 Vue 3 快速 Diff 代码 4. 性能优化分析4.1 性能测试数据4.2 内存使用对比 5. 使用场景分析5.1 Vu…...

编程日记 2025/8/16 5:58:16

启动桌面Docker提示虚拟服务未启动

在启动 Docker Desktop 时，可能会遇到以下提示： Docker Desktop - Virtual Machine Platform not enabled Virtual Machine Platform not enabled该错误通常是由于 Windows 未启用 “Virtual Machine Platform” 功能导致的，这是运行 Docker…...

编程日记 2025/8/16 5:57:54

【SpringBoot】实现登录功能

在上一篇博客中，我们讲解了注册页面的实现。在此基础上会跳转到登录页面，今天给大家带来的是使用 SpringBoot，MyBatis，Html，CSS，JavaScript，前后端交互实现一个登录功能。目录一、效果二、…...

编程日记 2025/8/15 6:15:46

DataWhale 速通AI编程开发：（进阶篇）第3章提示词（Prompts）配置项

学习网址：Datawhale-学用 AI,从此开始 3.1 Roo Code提示词配置了什么众所周知，提示词（Prompt）是用户向大语言模型输入的一段文本，用于指导大语言模型生成符合用户要求的输出。在ai编程领域更是如此，提示…...

编程日记 2025/8/16 1:35:32

VUE中VNode（虚拟节点）是个啥？

用 JavaScript 生成 Virtual DOM（VNode） 在 Vue 中，Virtual DOM（虚拟 DOM）是一个用 JavaScript 对象表示真实 DOM 结构的抽象层。通过这种方式，Vue 可以通过比较 Virtual DOM 与真实 DOM 的差异来最小化更…...

编程日记 2025/8/16 1:17:03

力扣：3. 无重复字符的最长子串（滑动窗口）

3. 无重复字符的最长子串 - 力扣（LeetCode）3. 无重复字符的最长子串 - 给定一个字符串 s ，请你找出其中不含有重复字符的最长子串的长度。示例 1:输入: s "abcabcbb"输出: 3 解释: 因为无重复字符的最长子串是 "abc"…...

编程日记 2025/8/16 5:57:40

注解+AOP实现权限控制

注解与AOP实战：实现权限控制在现代Java开发中，注解（Annotation）和面向切面编程（AOP）是两种强大的技术，它们能够帮助我们实现代码的解耦，提高代码的可读性和可维护性。本文将通过一…...

编程日记 2025/8/16 1:35:31

2.5 python接口编程

在现代软件开发的复杂生态系统中，不同系统、模块之间的交互协作至关重要。接口编程作为一种关键机制，定义了组件之间的通信规范与交互方式。Python 凭借其卓越的灵活性、丰富的库资源以及简洁易读的语法，在接口编程领域占据了重要地位&#x…...

编程日记 2025/8/16 5:56:10

睡不着运动锻炼贴士

在快节奏的现代生活中，失眠似乎已成为许多人的“夜间伴侣”。夜晚辗转反侧，白天精神不振，这样的恶性循环让许多人苦不堪言。其实，除了调整作息和饮食习惯，适当的运动也是改善睡眠的一剂良药。今天，就让我们…...

编程日记 2025/8/12 17:33:17

【Python入门】一篇掌握Python中的字典（创建、访问、修改、字典方法）【详细版】

🌈 个人主页：十二月的猫-CSDN博客 🔥 系列专栏： 🏀《Python/PyTorch极简课》_十二月的猫的博客-CSDN博客 💪🏻 十二月的寒冬阻挡不了春天的脚步，十二点的黑夜遮蔽不住黎明的曙光目…...

编程日记 2025/8/12 20:38:01

深入理解 HTML 表单与输入

在网页开发的广袤领域中，HTML 表单如同搭建用户与服务器沟通桥梁的基石。它是收集用户输入信息的关键渠道，承载着交互的重任。今天，就让我们一同深入探索 HTML 表单与输入的奥秘。 HTML 表单在文档中划定出一片独特的区域，这片…...

编程日记 2025/8/16 6:00:02

1、停止 Docker 服务 sudo systemctl stop docker2、迁移 Docker 数据目录 sudo mkdir -p /newpath/docker sudo rsync -avz /var/lib/docker/ /newpath/docker/3、修改 Docker 配置文件 vi /etc/docker/daemon.json 内容 {"data-root": "/newpath/docker&q…...

编程日记 2025/8/16 5:56:23

IPoIB驱动中RSS与TSS技术的深度解析：多队列机制与性能优化

在高速网络通信中，IP over InfiniBand（IPoIB）是实现低延迟、高吞吐的关键技术之一。为了充分发挥多核处理器的性能潜力，IPoIB驱动通过接收侧扩展（RSS）和发送侧扩展（TSS）技术，实现了数据包处理的多队列并行化。本文结合源码实现与性能优化策略，深入解析其核心机制…...

编程日记 2025/8/16 5:57:56

目前人工智能的发展，判断10年、20年后的人工智能发展的主要方向，或者带动的主要产业

根据2025年的最新行业研究和技术演进趋势，结合历史发展轨迹，未来10-20年人工智能发展的主要方向及带动的产业将呈现以下六大核心趋势： 一、算力革命与底层架构优化核心地位：算力将成为类似“新能源电池”的基础设施，…...

编程日记 2025/8/11 10:14:16

DeepSeek-prompt指令-当DeepSeek答非所问，应该如何准确的表达我们的诉求？

当DeepSeek答非所问，应该如何准确的表达我们的诉求？不同使用场景如何向DeepSeek发问？是否有指令公式？ 目录 1、扮演专家型指令2、知识蒸馏型指令3、颗粒度调节型指令4、时间轴推演型指令5、极端测试型6、逆向思维型指令7、…...

编程日记 2025/8/16 5:58:16

并发编程面试题二

1、java线程常见的基本状态有哪些，这些状态分别是做什么的 （1）创建（New）：new Thread()，生成线程对象。 （2）就绪（Runnable）:当调用线程对象的sta…...

编程日记 2025/8/16 5:59:25

【NLP】 8. 处理常见词（Stopwords）的不同策略

处理常见词（Stopwords）的不同策略在自然语言处理 (NLP) 和信息检索 (IR) 任务中，常见词（Stopwords） 是指在文本中频繁出现但通常对主要任务贡献较小的词，例如 “the”、“is”、“in”、“and” 等。这些…...

编程日记 2025/8/16 5:59:25

【Java基础】java中的lambda表达式

Java Lambda表达式深度解析：语法、简化规则与实战前言 Java 8的Lambda表达式通过简化匿名内部类和引入函数式编程，极大提升了代码的简洁性和可读性。一、Lambda表达式的核心语法 Lambda表达式由参数列表、->符号和表达式主体组成，其基…...

编程日记 2025/8/16 5:56:23

【RS】OneRec快手-生成式推荐模型

note 本文提出了一种名为 OneRec 的统一生成式推荐框架，旨在替代传统的多阶段排序策略，通过一个端到端的生成模型直接生成推荐结果。OneRec 的主要贡献包括： 编码器-解码器结构：采用稀疏混合专家（MoE）架构…...

编程日记 2025/8/16 5:56:09

DQN 玩 2048 实战｜第一期！搭建游戏环境（附 PyGame 可视化源码）

视频讲解： DQN 玩 2048 实战｜第一期！搭建游戏环境（附 PyGame 可视化源码） 代码仓库：GitHub - LitchiCheng/DRL-learning: 深度强化学习 2048游戏介绍，引用维基百科《2048》在44的网格上进行。…...

编程日记 2025/8/16 5:59:23

练习题：87

目录 Python题目题目题目分析代码实现代码解释列表推导式部分： 变量赋值和输出： 运行思路结束语 Python题目题目使用列表推导式生成一个包含 1 到 100 中所有偶数的列表。题目分析本题要求使用 Python 的列表推导式生成一个包含 …...

编程日记 2025/8/16 5:56:24

二叉树的层序遍历（102）

102. 二叉树的层序遍历 - 力扣（LeetCode） 解法： /*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeNode() : val(0), left(nullptr), right(nullptr) {}* …...

编程日记 2025/8/16 5:58:17

NVMe集群：加速数据处理

随着大数据和云计算的快速发展，企业面临着前所未有的数据处理挑战。传统的存储技术和架构已经难以满足现代应用对高性能和低延迟的需求。在这种背景下，NVMe（Non-Volatile Memory Express）集群应运而生，它以其卓越的性能…...

编程日记 2025/8/14 21:29:15

JUC并发编程：共享模型之管程

一、共享带来的问题 （1）Java的体现两个线程对初始值为 0 的静态变量一个做自增，一个做自减，各做 5000 次，结果是 0 吗？ （2）问题分析以上的结果可能是正数、负数、零。为什么呢…...

编程日记 2025/8/16 1:35:31

Java构造方法详解：从入门到实战

目录一、什么是构造方法？ 二、构造方法的作用三、构造方法分类与使用 1. 默认构造方法 2. 有参构造方法 3. 构造方法重载四、注意事项（避坑指南） 五、经典面试题解析六、实战应用场景七、总结一、什么是构造方法？ …...

编程日记 2025/8/16 6:00:01

Uniapp 字体加载问题(文件本地存储)

项目场景： 在最近公司开发一款小程序，但是小程序的文字需要用艺术字，就是那种不能用切图绕开的那种！ 问题描述我们在使用uni.loadfontface Api请求数据字体文件的时候总是会报错，就是那种网上也找不到解决方法的那种…...

编程日记 2025/8/16 5:56:23

HTML 新手入门：从零基础到搭建第一个静态页面（一）

开启 HTML 学习之旅在互联网的广袤世界中，网页是我们与信息交互的主要窗口。而 HTML，作为构建网页的基石，就像是搭建房屋的砖块，是网页开发中不可或缺的基础。无论你是对网页开发充满好奇的小白，还是渴望系统学习前端…...

编程日记 2025/8/13 8:11:11

使用multiprocessing实现进程间共享内存

在 Python 中，可以使用多种方法来实现几个进程之间的通信。简单消息传递：使用 multiprocessing.Queue 或 multiprocessing.Pipe。共享简单数据：使用 multiprocessing.Value 或 multiprocessing.Array。共享复杂数据：使用 multiprocessing.Manager。进程间信号控制：使用…...

编程日记 2025/8/16 5:59:26

在IDEA中连接达梦数据库：详细配置指南

达梦数据库（DM Database）作为国产关系型数据库的代表，广泛应用于企业级系统开发。本文将详细介绍如何在IntelliJ IDEA中配置并连接达梦数据库，助力开发者高效完成数据库开发工作。准备工作 1. 下载达梦JDBC驱动访问达梦官方资…...

编程日记 2025/8/16 5:56:22

docker无法正常拉取镜像问题的解决

目录 1.前言 2.解决方案 1.前言安装docker后拉取镜像，遇见了如下问题： Error response from daemon: Get "https://registry-1.docker.io/v2/": net/http: request canceled while waiting for connection (Client.Timeout exceeded whil…...

编程日记 2025/8/16 5:57:40

如何在保持安全/合规的同时更快地构建应用程序：DevOps 指南

随着敏捷思维方式的兴起，开发和 DevOps 团队都面临着持续的压力，他们需要以迭代方式缩短发布周期并加快部署速度，以满足不断增长的客户期望。随着这种对速度的追求越来越强烈，维护安全性和合规性标准的复杂性也随之增加。当今 D…...

编程日记 2025/8/16 5:58:16

SQL Server查询优化

最常用，最有效的数据库优化方式查询语句层面避免全表扫描使用索引：确保查询条件中的字段有索引。例如，查询语句 SELECT * FROM users WHERE age > 20，若 age 字段有索引，数据库会利用索引快速定位符合条件的记…...

编程日记 2025/8/16 5:57:40

iOS底层原理系列04-并发编程

在移动应用开发中，流畅的用户体验至关重要，而并发编程是实现这一目标的关键技术。本文将深入探讨iOS平台上的并发编程和多线程架构，帮助你构建高性能、响应迅速的应用程序。 1. iOS线程调度机制 1.1 线程本质和iOS线程调度机制线程是操作…...

编程日记 2025/8/16 5:57:41

企业数字化转型数据治理解决方案（119页PPT）（文末有下载方式)

资料解读：企业数字化转型数据治理解决方案详细资料请看本解读文章的最后内容。在当今数字化时代，数据已经成为企业最宝贵的资产之一。然而，随着数据量的激增和数据来源的多样化，如何有效管理和利用这些数据成为了企业面临的一…...

编程日记 2025/8/16 5:56:10

git报错：“fatal:refusing to merge unrelated histories“

新建仓库，克隆本地项目到新仓库，首次同步本地已提交的代码到远程时，报错："fatal:refusing to merge unrelated histories" 。报错意思是：致命的：拒绝合并无关的历史。一、问题背景&#xff…...

编程日记 2025/8/16 5:57:54

Jmeter下载及环境配置

Jmeter下载及环境配置 java环境变量配置配置jdk环境变量检查是否配置成功JMeter下载 java环境变量配置访问地址： https://www.oracle.com/cn/java/technologies/downloads/ 注意：需要自己注册账号下载完成，解压后的目录为： …...

编程日记 2025/8/16 5:57:55

K8S学习之基础二十四：k8s的持久化存储之pv和pvc

K8S的存储之pv和pvc 在 Kubernetes (k8s) 中，持久化存储是通过 PersistentVolume (PV) 和 PersistentVolumeClaim (PVC) 来实现的。PVC 是用户对存储资源的请求，而 PV 是集群中的实际存储资源。PVC 和 PV 的关系类似于 Pod 和 Node 的关系。 Persisten…...

编程日记 2025/8/16 5:59:26

1.5、Java构造方法重载

构造方法重载的实现 （1）定义多个构造方法 class Person {private String name;private int age;// 无参构造方法public Person() {this.name "Unknown";this.age 0;}// 带一个参数的构造方法public Person(String name) {this.name name;…...

编程日记 2025/8/6 21:34:49

领域驱动设计(DDD)技术分享：从三层架构到DDD的进化之旅

一、开篇话：我们为什么要聊DDD？ 如果你像我一样有着Java开发背景，那Spring的三层架构可能是你的老朋友了。Controller-Service-DAO这种模式简直就像我们编程的"家常便饭"。但是，随着业务越来越复杂，你是否也…...

编程日记 2025/8/13 17:29:55

LeetCode - #227 基于 Swift 实现基本计算器

摘要在这篇文章中，我们将实现一个基于 Swift 语言的基本计算器。该计算器能够解析和计算包含、-、* 和 / 的数学表达式，并且遵循运算符的优先级规则。整数除法仅保留整数部分，不能使用 eval() 这样的内置解析方法。描述给你一个字符串表…...

编程日记 2025/8/13 14:12:22

Elasticsearch Java High Level Client [7.17] 使用

es 的 HighLevelClient存在es源代码的引用，结合springboot使用时，会存在es版本的冲突，这里记录下解决冲突和使用方式（es已经不建议使用这个了）。注意es服务端的版本需要与client的版本对齐，否则返回数据可…...

编程日记 2025/8/13 1:30:16

[多线程]基于环形队列（RingQueue）的生产者-消费者模型的实现

标题：[多线程]基于环形队列（RingQueue）的生产者-消费者模型水墨不写bug 一、模型实现接下来我们要实现一个基于环形队列（RingQueue）的生产者-消费者模型。该模型使用信号量和互斥锁来保证生产者和消费者之间的同步与…...

编程日记 2025/8/14 19:42:09

HAL库STM32常用外设—— CAN通信（一）

文章目录一、CAN是什么？1.1 CAN应用场景1.2 CAN通信优势二、CAN基础知识介绍2.1 CAN总线结构2.2 CAN总线特点2.2.1 CAN总线的数据传输特点2.2.2 位时序和波特率 2.3 CAN位时序和波特率2.3 CAN物理层2.3.1 CAN 物理层特性2.3.2 CAN 收发器芯片介绍 2.4 CAN协议层2.…...

编程日记 2025/8/6 14:27:35

分页查询的实现

目录前言一.问题描述二.后端实现步骤 2.1配置PageHelper插件 ①导入依赖 ②在application.yml配置文件中添加相关配置 2.2编写一个入门的程序，体验分页过程 2.3定义一个vo，用来收集分页后的所有信息 2.4修改serviceImpl层的代码 2.5动态设…...

编程日记 2025/8/15 14:34:36

KMP算法深度解析

一、从暴力匹配到智能跳转：

经典场景对比

二、KMP核心机制：部分匹配表的精妙设计

2.1 最长公共前后缀（LPS）计算

2.2 next数组生成算法

三、KMP算法实现详解

3.1 匹配过程可视化

3.2 复杂度分析

四、KMP的优化演进

4.1 Next数组优化版

4.2 应用场景对比

工业级应用案例

生物信息学的DNA序列匹配

敏感词过滤系统

思维革命

相关文章：