算法——KMP算法(Knuth-Morris-Pratt算法)
KMP算法(Knuth-Morris-Pratt算法)是一种高效的字符串匹配算法,用于在主文本字符串中快速查找模式字符串的出现位置。其核心思想是通过预处理模式字符串,利用部分匹配信息(即“失败函数”或“next数组”)避免在匹配失败时回溯主串,从而将时间复杂度优化到 O(n+m)(n是主串长度,m是模式串长度),远优于暴力匹配算法的 O(n×m)。
一,核心原理
-
部分匹配表(Prefix Table / Next数组)
- 定义:
next[i]表示模式串的子串P[0...i]的最长公共前后缀长度。 - 作用:当字符匹配失败时,根据
next数组决定模式串的回溯位置,避免重复比较主串。
- 定义:
-
匹配过程
- 主串指针不回溯,仅移动模式串指针:
若当前字符匹配失败,模式串指针回退到next[j]的位置继续匹配。
- 主串指针不回溯,仅移动模式串指针:
二,Next数组的构建
最长前缀概念: 最长前缀是说以第一个字符开始,但是不包含最后一个字符。
最长后缀概念: 最长后缀是说以最后一个字符开始,但是不包含第一个字符。
next 数组定义:在模式串中(下标从0开始),next[i] 表示模式串中以下标 i 处字符结尾的子串的最大相同前后缀的长度。在KMP算法中,该值一方面表示模式串中1~i位置子串中的最长相同前后缀长度,另一方面表示在该位置匹配失败时模式串回溯比较的下一个字符位置(最长前缀末座标的下一个字符)
步骤示例(模式串 P = "ABABCABAB")
| 索引 | 子串 | 最长公共前后缀 | next[i] |
|---|---|---|---|
| 0 | A | 无 | 0 |
| 1 | AB | 无 | 0 |
| 2 | ABA | “A” | 1 |
| 3 | ABAB | “AB” | 2 |
| 4 | ABABC | 无 | 0 |
| 5 | ABABCA | “A” | 1 |
| 6 | ABABCAB | “AB” | 2 |
| 7 | ABABCABA | “ABA” | 3 |
| 8 | ABABCABAB | “ABAB” | 4 |
最终 next = [0, 0, 1, 2, 0, 1, 2, 3, 4]。
构建代码(Python)
def build_next(pattern):next = [0] * len(pattern)j = 0 # 前缀末尾指针for i in range(1, len(pattern)): # 后缀末尾指针while j > 0 and pattern[i] != pattern[j]:j = next[j-1] # 回退到前一个匹配位置if pattern[i] == pattern[j]:j += 1next[i] = jreturn next# 示例:模式串 "ABABCABAB"
print(build_next("ABABCABAB")) # 输出 [0, 0, 1, 2, 0, 1, 2, 3, 4]
三,匹配过程代码(Python)
def kmp_search(text, pattern):next = build_next(pattern)j = 0 # 模式串指针for i in range(len(text)): # 主串指针while j > 0 and text[i] != pattern[j]:j = next[j-1] # 模式串回退if text[i] == pattern[j]:j += 1if j == len(pattern):return i - j + 1 # 返回匹配的起始位置return -1# 示例
text = "ABABABCABABABD"
pattern = "ABABCABAB"
print(kmp_search(text, pattern)) # 输出 2(从索引2开始匹配)
多次出现的位置
def kmp_search(text, pattern):index = [] next = build_next(pattern)j = 0 # 模式串指针for i in range(len(text)): # 主串指针while j > 0 and text[i] != pattern[j]:j = next[j-1] # 模式串回退if text[i] == pattern[j]:j += 1if j == len(pattern):#return i - j + 1 # 返回匹配的起始位置index.append(i - j + 1)j = next[j-1]return index
匹配失败时:失败位置之前的主串(i前)和子串(j前)部分一定都是匹配的。且对于子串来说,失败位置之前(j前)的任一部分属于子串(模式串)的这段子串(子子串)的后缀
重新匹配时:我们重新匹配的开始一定是子串(模式串)的某部分前缀
要想移动子串(模式串)指针(i 下次匹配位置)到最大有效匹配位置,那么这个位置一定是这段前缀=后缀的部分
四,关键点
-
时间复杂度
- 预处理模式串构建
next数组:O(m) - 匹配过程:O(n)
- 总体:O(n + m).
- 预处理模式串构建
-
优势
- 避免主串指针回溯,适合处理大文本流或实时数据。
-
应用场景
- 文本编辑器中的查找功能(如Ctrl+F)、代码解析、DNA序列匹配等。
无,对比暴力匹配
- 暴力匹配:每次失配后,主串和模式串指针均回退,重复比较已匹配的字符。
主串:A B A B A B C 模式:A B A B C 暴力匹配需要回退主串指针,比较多次。 - KMP:主串指针不回溯,仅调整模式串指针,效率显著提升。
掌握KMP算法的核心在于理解部分匹配表的构建逻辑和失配时的回溯策略。
相关文章:
算法——KMP算法(Knuth-Morris-Pratt算法)
KMP算法(Knuth-Morris-Pratt算法)是一种高效的字符串匹配算法,用于在主文本字符串中快速查找模式字符串的出现位置。其核心思想是通过预处理模式字符串,利用部分匹配信息(即“失败函数”或“next数组”)避免…...
一周学会Flask3 Python Web开发-flask3模块化blueprint配置
锋哥原创的Flask3 Python Web开发 Flask3视频教程: 2025版 Flask3 Python web开发 视频教程(无废话版) 玩命更新中~_哔哩哔哩_bilibili 我们在项目开发的时候,多多少少会划分几个或者几十个业务模块,如果把这些模块的视图方法都写在app.py…...
Pytorch实现之统计全局信息的轻量级EGAN
简介 简介:模型在EGAN的基础上改进了一个降维的自注意力机制,并且设计了一个新颖的选择算子,使用轮盘赌来选择个体,如果他们的适配度满足fchild<VALUE,则被选中的个体将被丢弃。需要在进化的初始阶段尽快找到最佳个体,并在后续阶段保持种群的多样性。 论文题目:LGE…...
Java开发实习面试笔试题(含答案)
在广州一家中大公司面试(BOSS标注是1000-9999人,薪资2-3k),招聘上写着Java开发,基本没有标注前端要求,但是到场知道是前后端分离人不分离。开始先让你做笔试(12道问答4道SQL题)&…...
《论模型驱动架构设计方法及其应用》审题技巧 - 系统架构设计师
软件测试工程师软考论文写作框架 一、考点概述 “模型驱动架构设计及其应用”这一论题,主要考察了考生对模型驱动架构设计(MDA)这一先进软件设计方法的理解与应用能力。论题涵盖了MDA的基本概念、核心要素、实施流程及在实际项目中的应用等…...
【服务器与本地互传文件】远端服务器的Linux系统 和 本地Windows系统 互传文件
rz 命令:本地上传到远端 rz 命令:用于从本地主机上传文件到远程服务器 rz 是一个用于在 Linux 系统中通过 串口 或 SSH 上传文件的命令,它实际上是 lrzsz 工具包中的一个命令。rz 命令可以调用一个图形化的上传窗口,方便用户从本…...
初学者如何设置以及使用富文本编辑器[eclipse版]
手把手教你设置富文本编辑器 参考来源:UEditor Docs 初学者按我的步骤来就可以啦 一、设置ueditor编辑器 1.提取文件[文章最底部有链接提取方式] 2.解压文件并放到自己项目中,在WebContent目录下: 3. 修改jar包位置路径 到--> 注意&a…...
在 Java 中解析 JSON 数据
例子解析以下JSON数据 {"code":0,"msg":"成功","data": [{ "host":"1068222.com", "port":"", "m_token":"490e20e70e7de5f21a24b14c12a393f6", "categ…...
Python爬虫实战:从零到一构建数据采集系统
文章目录 前言一、准备工作1.1 环境配置1.2 选择目标网站 二、爬虫实现步骤2.1 获取网页内容2.2 解析HTML2.3 数据保存 三、完整代码示例四、优化与扩展4.1 反爬应对策略4.2 动态页面处理4.3 数据可视化扩展 五、注意事项六、总结互动环节 前言 在大数据时代,数据采…...
SpringCloud系列教程:微服务的未来(二十五)-基于注解的声明队列交换机、消息转换器、业务改造
前言 在现代分布式系统中,消息队列是实现服务解耦和异步处理的关键组件。Spring框架提供了强大的支持,使得与消息队列(如RabbitMQ、Kafka等)的集成变得更加便捷和灵活。本文将深入探讨如何利用Spring的注解驱动方式来配置和管理队…...
Opengl常用缓冲对象功能介绍及使用示例(C++实现)
本文整理了常用的opengl缓冲区对象并安排了使用示例 名称英文全称作用简述顶点数组对象Vertex Array Object (VAO)管理 VBO 和 EBO 的配置,存储顶点属性设置,简化渲染流程,避免重复设置状态顶点缓冲区对象Vertex Buffer Object (VBO)存储顶点…...
docker独立部署milvus向量数据库
milvus镜像:国外封锁,国内源也不好用。基本上所有源都不能用 首先想到阿里云服务,但是阿里云国外服务器便宜的300~400呢。 基于成本考虑终于装上心心念念的milvus(*^▽^*) 安装 Milvus 安装 Milvus 独立版 wget https://raw.githubuserco…...
【JT/T 808协议】808 协议开发笔记 ② ( 终端注册 | 终端注册应答 | 字符编码转换网站 )
文章目录 一、消息头 数据1、消息头拼接2、消息 ID 字段3、消息体属性 字段4、终端手机号 字段5、终端流水号 字段 二、消息体 数据三、校验码计算四、最终计算结果五、终端注册应答1、分解终端应答数据2、终端应答 消息体 数据 六、字符编码转换网站 一、消息头 数据 1、消息头…...
github配置sshkey
使用命令生成sshkey ssh-keygen -t rsa -b 4096 -C "your_emailexample.com" 依此会要求输入以下信息,可以使用默认值 设置保存密钥的路径 设置SSH密钥密码(备注:空内容表示不设置SSH密钥密码) 再次确认SSH密钥密…...
Java数据结构第十二期:走进二叉树的奇妙世界(一)
专栏:数据结构(Java版) 个人主页:手握风云 目录 一、树型结构 1.1. 树的定义 1.2. 树的基本概念 1.3. 树的表示形式 二、二叉树 2.1. 概念 2.2. 两种特殊的二叉树 2.3. 二叉树的性质 2.4. 二叉树的存储 三、二叉树的基本操作 一、树型结构 1.…...
Web的增删改查
准备环境 1. 添加web 点击项目右键——>选择**添加框架**选择**web应用程序** 2.创建lib目录 在web应用程序的**WEB-INF目录下**创建lib目录添加jar包(5个)解压:右键——>选择**添加库** 3.创建Dao层 在src目录下创建包com.zmq在该包下创建dao层添加工具…...
Java 前后端时间格式转换
在 Web 开发里,时间格式处理既常见又关键。由于前端和后端对时间的表示、处理方式存在差异,熟练掌握时间格式的转换方法就显得尤为重要。这篇文章会深入探讨 Java 前后端时间格式转换的相关知识,特别是 Java 时间转换的多种方式,其…...
【用deepseek和chatgpt做算法竞赛】——还得DeepSeek来 -Minimum Cost Trees_5
往期 【用deepseek和chatgpt做算法竞赛】——华为算法精英实战营第十九期-Minimum Cost Trees_0:介绍了题目和背景【用deepseek和chatgpt做算法竞赛】——华为算法精英实战营第十九期-Minimum Cost Trees_1:题目输入的格式说明,选择了邻接表…...
C++ 互斥锁的使用
mutex std::mutex 是C标准库中用于线程同步的互斥锁机制,主要用于保护共享资源,避免多个线程同时访问导致的竞态条件。 它提供了以下功能: 加锁(lock):阻塞当前线程,直到获取锁。 解锁&#…...
【Elasticsearch】Retrieve inner hits获取嵌套查询的具体的嵌套文档来源,以及父子文档的来源
Retrieve inner hits 是 Elasticsearch 中的一个功能,用于在嵌套查询或父子查询中,返回导致主文档匹配的具体嵌套对象或子/父文档的详细信息,帮助用户更直观地理解查询结果的来源。 在 Elasticsearch 中,Retrieve inner hits是一…...
利用ngx_stream_return_module构建简易 TCP/UDP 响应网关
一、模块概述 ngx_stream_return_module 提供了一个极简的指令: return <value>;在收到客户端连接后,立即将 <value> 写回并关闭连接。<value> 支持内嵌文本和内置变量(如 $time_iso8601、$remote_addr 等)&a…...
【力扣数据库知识手册笔记】索引
索引 索引的优缺点 优点1. 通过创建唯一性索引,可以保证数据库表中每一行数据的唯一性。2. 可以加快数据的检索速度(创建索引的主要原因)。3. 可以加速表和表之间的连接,实现数据的参考完整性。4. 可以在查询过程中,…...
前端倒计时误差!
提示:记录工作中遇到的需求及解决办法 文章目录 前言一、误差从何而来?二、五大解决方案1. 动态校准法(基础版)2. Web Worker 计时3. 服务器时间同步4. Performance API 高精度计时5. 页面可见性API优化三、生产环境最佳实践四、终极解决方案架构前言 前几天听说公司某个项…...
23-Oracle 23 ai 区块链表(Blockchain Table)
小伙伴有没有在金融强合规的领域中遇见,必须要保持数据不可变,管理员都无法修改和留痕的要求。比如医疗的电子病历中,影像检查检验结果不可篡改行的,药品追溯过程中数据只可插入无法删除的特性需求;登录日志、修改日志…...
Debian系统简介
目录 Debian系统介绍 Debian版本介绍 Debian软件源介绍 软件包管理工具dpkg dpkg核心指令详解 安装软件包 卸载软件包 查询软件包状态 验证软件包完整性 手动处理依赖关系 dpkg vs apt Debian系统介绍 Debian 和 Ubuntu 都是基于 Debian内核 的 Linux 发行版ÿ…...
Cilium动手实验室: 精通之旅---20.Isovalent Enterprise for Cilium: Zero Trust Visibility
Cilium动手实验室: 精通之旅---20.Isovalent Enterprise for Cilium: Zero Trust Visibility 1. 实验室环境1.1 实验室环境1.2 小测试 2. The Endor System2.1 部署应用2.2 检查现有策略 3. Cilium 策略实体3.1 创建 allow-all 网络策略3.2 在 Hubble CLI 中验证网络策略源3.3 …...
工程地质软件市场:发展现状、趋势与策略建议
一、引言 在工程建设领域,准确把握地质条件是确保项目顺利推进和安全运营的关键。工程地质软件作为处理、分析、模拟和展示工程地质数据的重要工具,正发挥着日益重要的作用。它凭借强大的数据处理能力、三维建模功能、空间分析工具和可视化展示手段&…...
剑指offer20_链表中环的入口节点
链表中环的入口节点 给定一个链表,若其中包含环,则输出环的入口节点。 若其中不包含环,则输出null。 数据范围 节点 val 值取值范围 [ 1 , 1000 ] [1,1000] [1,1000]。 节点 val 值各不相同。 链表长度 [ 0 , 500 ] [0,500] [0,500]。 …...
srs linux
下载编译运行 git clone https:///ossrs/srs.git ./configure --h265on make 编译完成后即可启动SRS # 启动 ./objs/srs -c conf/srs.conf # 查看日志 tail -n 30 -f ./objs/srs.log 开放端口 默认RTMP接收推流端口是1935,SRS管理页面端口是8080,可…...
2021-03-15 iview一些问题
1.iview 在使用tree组件时,发现没有set类的方法,只有get,那么要改变tree值,只能遍历treeData,递归修改treeData的checked,发现无法更改,原因在于check模式下,子元素的勾选状态跟父节…...
