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

算法——KMP算法(Knuth-Morris-Pratt算法)

KMP算法(Knuth-Morris-Pratt算法)是一种高效的字符串匹配算法,用于在主文本字符串中快速查找模式字符串的出现位置。其核心思想是通过预处理模式字符串,利用部分匹配信息(即“失败函数”或“next数组”)避免在匹配失败时回溯主串,从而将时间复杂度优化到 O(n+m)(n是主串长度,m是模式串长度),远优于暴力匹配算法的 O(n×m)


一,核心原理

  1. 部分匹配表(Prefix Table / Next数组)

    • 定义:next[i] 表示模式串的子串 P[0...i]最长公共前后缀长度
    • 作用:当字符匹配失败时,根据 next 数组决定模式串的回溯位置,避免重复比较主串。
  2. 匹配过程

    • 主串指针不回溯,仅移动模式串指针:
      若当前字符匹配失败,模式串指针回退到 next[j] 的位置继续匹配。

二,Next数组的构建

最长前缀概念: 最长前缀是说以第一个字符开始,但是不包含最后一个字符。
最长后缀概念: 最长后缀是说以最后一个字符开始,但是不包含第一个字符。
next 数组定义:在模式串中(下标从0开始),next[i] 表示模式串中以下标 i 处字符结尾的子串的最大相同前后缀的长度。在KMP算法中,该值一方面表示模式串中1~i位置子串中的最长相同前后缀长度,另一方面表示在该位置匹配失败时模式串回溯比较的下一个字符位置(最长前缀末座标的下一个字符)

步骤示例(模式串 P = "ABABCABAB"

索引子串最长公共前后缀next[i]
0A0
1AB0
2ABA“A”1
3ABAB“AB”2
4ABABC0
5ABABCA“A”1
6ABABCAB“AB”2
7ABABCABA“ABA”3
8ABABCABAB“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 下次匹配位置)到最大有效匹配位置,那么这个位置一定是这段前缀=后缀的部分

四,关键点

  1. 时间复杂度

    • 预处理模式串构建 next 数组:O(m)
    • 匹配过程:O(n)
    • 总体:O(n + m).
  2. 优势

    • 避免主串指针回溯,适合处理大文本流实时数据
  3. 应用场景

    • 文本编辑器中的查找功能(如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开发实习面试笔试题(含答案)

在广州一家中大公司面试&#xff08;BOSS标注是1000-9999人&#xff0c;薪资2-3k&#xff09;&#xff0c;招聘上写着Java开发&#xff0c;基本没有标注前端要求&#xff0c;但是到场知道是前后端分离人不分离。开始先让你做笔试&#xff08;12道问答4道SQL题&#xff09;&…...

《论模型驱动架构设计方法及其应用》审题技巧 - 系统架构设计师

软件测试工程师软考论文写作框架 一、考点概述 “模型驱动架构设计及其应用”这一论题&#xff0c;主要考察了考生对模型驱动架构设计&#xff08;MDA&#xff09;这一先进软件设计方法的理解与应用能力。论题涵盖了MDA的基本概念、核心要素、实施流程及在实际项目中的应用等…...

【服务器与本地互传文件】远端服务器的Linux系统 和 本地Windows系统 互传文件

rz 命令&#xff1a;本地上传到远端 rz 命令&#xff1a;用于从本地主机上传文件到远程服务器 rz 是一个用于在 Linux 系统中通过 串口 或 SSH 上传文件的命令&#xff0c;它实际上是 lrzsz 工具包中的一个命令。rz 命令可以调用一个图形化的上传窗口&#xff0c;方便用户从本…...

初学者如何设置以及使用富文本编辑器[eclipse版]

手把手教你设置富文本编辑器 参考来源&#xff1a;UEditor Docs 初学者按我的步骤来就可以啦 一、设置ueditor编辑器 1.提取文件[文章最底部有链接提取方式] 2.解压文件并放到自己项目中&#xff0c;在WebContent目录下&#xff1a; 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 数据可视化扩展 五、注意事项六、总结互动环节 前言 在大数据时代&#xff0c;数据采…...

SpringCloud系列教程:微服务的未来(二十五)-基于注解的声明队列交换机、消息转换器、业务改造

前言 在现代分布式系统中&#xff0c;消息队列是实现服务解耦和异步处理的关键组件。Spring框架提供了强大的支持&#xff0c;使得与消息队列&#xff08;如RabbitMQ、Kafka等&#xff09;的集成变得更加便捷和灵活。本文将深入探讨如何利用Spring的注解驱动方式来配置和管理队…...

Opengl常用缓冲对象功能介绍及使用示例(C++实现)

本文整理了常用的opengl缓冲区对象并安排了使用示例 名称英文全称作用简述顶点数组对象Vertex Array Object (VAO)管理 VBO 和 EBO 的配置&#xff0c;存储顶点属性设置&#xff0c;简化渲染流程&#xff0c;避免重复设置状态顶点缓冲区对象Vertex Buffer Object (VBO)存储顶点…...

docker独立部署milvus向量数据库

milvus镜像&#xff1a;国外封锁&#xff0c;国内源也不好用。基本上所有源都不能用 首先想到阿里云服务&#xff0c;但是阿里云国外服务器便宜的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" 依此会要求输入以下信息&#xff0c;可以使用默认值 设置保存密钥的路径 设置SSH密钥密码&#xff08;备注&#xff1a;空内容表示不设置SSH密钥密码&#xff09; 再次确认SSH密钥密…...

Java数据结构第十二期:走进二叉树的奇妙世界(一)

专栏&#xff1a;数据结构(Java版) 个人主页&#xff1a;手握风云 目录 一、树型结构 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个)解压&#xff1a;右键——>选择**添加库** 3.创建Dao层 在src目录下创建包com.zmq在该包下创建dao层添加工具…...

Java 前后端时间格式转换

在 Web 开发里&#xff0c;时间格式处理既常见又关键。由于前端和后端对时间的表示、处理方式存在差异&#xff0c;熟练掌握时间格式的转换方法就显得尤为重要。这篇文章会深入探讨 Java 前后端时间格式转换的相关知识&#xff0c;特别是 Java 时间转换的多种方式&#xff0c;其…...

【用deepseek和chatgpt做算法竞赛】——还得DeepSeek来 -Minimum Cost Trees_5

往期 【用deepseek和chatgpt做算法竞赛】——华为算法精英实战营第十九期-Minimum Cost Trees_0&#xff1a;介绍了题目和背景【用deepseek和chatgpt做算法竞赛】——华为算法精英实战营第十九期-Minimum Cost Trees_1&#xff1a;题目输入的格式说明&#xff0c;选择了邻接表…...

C++ 互斥锁的使用

mutex std::mutex 是C标准库中用于线程同步的互斥锁机制&#xff0c;主要用于保护共享资源&#xff0c;避免多个线程同时访问导致的竞态条件。 它提供了以下功能&#xff1a; 加锁&#xff08;lock&#xff09;&#xff1a;阻塞当前线程&#xff0c;直到获取锁。 解锁&#…...

【Elasticsearch】Retrieve inner hits获取嵌套查询的具体的嵌套文档来源,以及父子文档的来源

Retrieve inner hits 是 Elasticsearch 中的一个功能&#xff0c;用于在嵌套查询或父子查询中&#xff0c;返回导致主文档匹配的具体嵌套对象或子/父文档的详细信息&#xff0c;帮助用户更直观地理解查询结果的来源。 在 Elasticsearch 中&#xff0c;Retrieve inner hits是一…...

8k长序列建模,蛋白质语言模型Prot42仅利用目标蛋白序列即可生成高亲和力结合剂

蛋白质结合剂&#xff08;如抗体、抑制肽&#xff09;在疾病诊断、成像分析及靶向药物递送等关键场景中发挥着不可替代的作用。传统上&#xff0c;高特异性蛋白质结合剂的开发高度依赖噬菌体展示、定向进化等实验技术&#xff0c;但这类方法普遍面临资源消耗巨大、研发周期冗长…...

LeetCode - 394. 字符串解码

题目 394. 字符串解码 - 力扣&#xff08;LeetCode&#xff09; 思路 使用两个栈&#xff1a;一个存储重复次数&#xff0c;一个存储字符串 遍历输入字符串&#xff1a; 数字处理&#xff1a;遇到数字时&#xff0c;累积计算重复次数左括号处理&#xff1a;保存当前状态&a…...

vue3 字体颜色设置的多种方式

在Vue 3中设置字体颜色可以通过多种方式实现&#xff0c;这取决于你是想在组件内部直接设置&#xff0c;还是在CSS/SCSS/LESS等样式文件中定义。以下是几种常见的方法&#xff1a; 1. 内联样式 你可以直接在模板中使用style绑定来设置字体颜色。 <template><div :s…...

Qwen3-Embedding-0.6B深度解析:多语言语义检索的轻量级利器

第一章 引言&#xff1a;语义表示的新时代挑战与Qwen3的破局之路 1.1 文本嵌入的核心价值与技术演进 在人工智能领域&#xff0c;文本嵌入技术如同连接自然语言与机器理解的“神经突触”——它将人类语言转化为计算机可计算的语义向量&#xff0c;支撑着搜索引擎、推荐系统、…...

【Zephyr 系列 10】实战项目:打造一个蓝牙传感器终端 + 网关系统(完整架构与全栈实现)

🧠关键词:Zephyr、BLE、终端、网关、广播、连接、传感器、数据采集、低功耗、系统集成 📌目标读者:希望基于 Zephyr 构建 BLE 系统架构、实现终端与网关协作、具备产品交付能力的开发者 📊篇幅字数:约 5200 字 ✨ 项目总览 在物联网实际项目中,**“终端 + 网关”**是…...

NLP学习路线图(二十三):长短期记忆网络(LSTM)

在自然语言处理(NLP)领域,我们时刻面临着处理序列数据的核心挑战。无论是理解句子的结构、分析文本的情感,还是实现语言的翻译,都需要模型能够捕捉词语之间依时序产生的复杂依赖关系。传统的神经网络结构在处理这种序列依赖时显得力不从心,而循环神经网络(RNN) 曾被视为…...

力扣-35.搜索插入位置

题目描述 给定一个排序数组和一个目标值&#xff0c;在数组中找到目标值&#xff0c;并返回其索引。如果目标值不存在于数组中&#xff0c;返回它将会被按顺序插入的位置。 请必须使用时间复杂度为 O(log n) 的算法。 class Solution {public int searchInsert(int[] nums, …...

如何在网页里填写 PDF 表格?

有时候&#xff0c;你可能希望用户能在你的网站上填写 PDF 表单。然而&#xff0c;这件事并不简单&#xff0c;因为 PDF 并不是一种原生的网页格式。虽然浏览器可以显示 PDF 文件&#xff0c;但原生并不支持编辑或填写它们。更糟的是&#xff0c;如果你想收集表单数据&#xff…...

git: early EOF

macOS报错&#xff1a; Initialized empty Git repository in /usr/local/Homebrew/Library/Taps/homebrew/homebrew-core/.git/ remote: Enumerating objects: 2691797, done. remote: Counting objects: 100% (1760/1760), done. remote: Compressing objects: 100% (636/636…...

DAY 45 超大力王爱学Python

来自超大力王的友情提示&#xff1a;在用tensordoard的时候一定一定要用绝对位置&#xff0c;例如&#xff1a;tensorboard --logdir"D:\代码\archive (1)\runs\cifar10_mlp_experiment_2" 不然读取不了数据 知识点回顾&#xff1a; tensorboard的发展历史和原理tens…...