字符串的KMP算法详解及C/C++代码实现
1. 原由
紧接上文,我们知道了暴力匹配的算法在时间运行上的缺陷,假设字符串T的长度为n,字符串P的长度为m,则整个算法的时间复杂度为O( n * m ),而对于一个复杂的现实情况而言 n >> m >> 2 (即n远远大于m,m远远大于常数),这样的计算计算机的负担很重。
请思考一个暴力匹配的情况:
给定一个主字符串
T = “AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAB”(47位)
同时给定模式串 P = “AAAAAB”(6位)
试问搜索的情况,很显然,暴力搜索对于每一次搜索,都要搜索到最后一个字符才能进行下一轮的搜索,因此进行的计算近似可以理解为:O(47 * 6) ,对于这样很少的数据已经有很高的计算量了。
KMP算法一种改进的模式匹配算法,是D.E.Knuth、V.R.Pratt、J.H.Morris于1977年联合发表,KMP算法又称克努特-莫里斯-普拉特操作, KMP算法与前文的暴力匹配算法,核心的区别就是没有不匹配的回溯,而是根据整个字符串的情况进行一次位移,这样大大减少了回溯产生的缺陷,KMP算法的时间复杂度可以优化到 O( n + m)级别,是二次优化到线性的程度。
2.构造next表(以-1开头)
对于模式串P而言,我们需要知道模式串中P的每一位的前一位是否存在相等的完全相等的前后缀,并且求这个最大的完全相等的前后缀,如一个模式串”ABCABDE”对于第倒数第二位字符而言,其符合情况的前后缀就是”AB”,而最后一位则没有完全相等的前后缀。
PS:何为前后缀:如一个字符串”ABCD”,其前缀有可能为”A”“AB”“ABC”(即除去本身的全部字符),同理,则后缀可能为:”D””CD””BCD”
我们需要求的就是每一个字符其相对应的最大前后缀数,这样与模式串P一一对应的表称之为next表。
因此”ABCABDE”的next表为:-1 0 0 0 1 2 0 (字符用空格隔开)
那么我们该如何实现代码呢?
对于每一个当前需要判断的字符而言,在构造next表时,应该向前进行比对,以上一个已经判断的情况为基础(初始值赋-1,部分教程中初始值赋0,两者没有实质区别),后缀如果+1位置的字符与前缀+1位置的字符相等,则next[i]就是next[i-1]+1,而如果不相等,则说明无法匹配,则next[i]=0。
3. KMP实现
与暴力匹配极其相似,利用while循环的条件控制, 进行匹配失败时,只需要将失败的模式串P的索引指向next表中对应的数值即可,其余匹配照旧线性执行即可。
4. 实现代码(仅作参考)
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;int *buildNext(char *P){int m = strlen(P) , j=0;int * N = new int[m];int t = N[0] = -1;while( j < m-1 ){if( 0 > t || P[j] == P[t] ){N[++j] = ++t;}else{t = N[t];}}return N;
}int KMP(char T[],char P[]){ //T--主串,P--模式串int *next = buildNext(P); //构造NEXT表int n = strlen(T) , i=0;int m = strlen(P) , j=0;while( j<m && i<n ){if( j<0 || T[i]==P[j] ){i++;j++;}else{j = next[j];}}delete []next;return i-j;
}int main(){char org[] = "ABABABABABD";char str[] = "ABABD";int ans = KMP(org,str);cout << ans <<endl;return 0;
}
输出6,即经过6位,在第七位发生匹配
相关文章:
字符串的KMP算法详解及C/C++代码实现
1. 原由 紧接上文,我们知道了暴力匹配的算法在时间运行上的缺陷,假设字符串T的长度为n,字符串P的长度为m,则整个算法的时间复杂度为O( n * m ),而对于一个复杂的现实情况而言 n >> m >> 2 (即…...

2024年数学建模比赛题目及解题代码
目录 一、引言 1. 1竞赛背景介绍 1.1.1数学建模竞赛概述 1.1.2生产过程决策问题在竞赛中的重要性 1.2 解题前准备 1.2.2 工具与资源准备 1.2.3 心态调整与策略规划 二、问题理解与分析 三、模型构建与求解 3.1 模型选择与设计 3.1.1 根据问题特性选择合适的数学模型类…...

BERT 论文逐段精读【论文精读】
BERT: 近 3 年 NLP 最火 CV: 大数据集上的训练好的 NN 模型,提升 CV 任务的性能 —— ImageNet 的 CNN 模型 NLP: BERT 简化了 NLP 任务的训练,提升了 NLP 任务的性能 BERT 如何站在巨人的肩膀上的?使用了哪些 NLP 已有的技术和思想ÿ…...
在Flask中实现跨域请求(CORS)
在Flask中实现跨域请求(CORS,Cross-Origin Resource Sharing)主要涉及到对Flask应用的配置,以允许来自不同源的请求访问服务器上的资源。以下是在Flask中实现CORS的详细步骤和方法: 一、理解CORS CORS是一种机制&…...

在桌面商业分析应用程序中启用高级 Web UI
挑战 Mercur Business Control 应用程序在企业界,尤其是金融领域,拥有悠久的应用历史。它帮助企业处理、可视化和分析海量数据,从而做出明智的商业决策。 随着产品的不断演进和现代化,Mercur Solutions AB 为该应用创建了 Web 客…...

CentOS Stream 8 通过 Packstack 安装开源 OpenStack(V版)
1、环境规划以及网卡配置 controller IP:192.168.235.101 compute IP:192.168.235.102 控制节点 [rootluck ~]# cd /etc/sysconfig/network-scripts/ [rootluck network-scripts]# vi ifcfg-ens160 [rootluck network-scripts]# cat ifcfg-ens160 TYP…...
OpenSSL工具验证RSA证书
openssl x509 是一个用于处理 X.509 证书的命令行工具。常用的 openssl x509 命令: -in <file>:指定输入文件。-out <file>:指定输出文件。-noout:不输出证书信息。-text:以文本格式输出证书信息。-pubke…...

架构师白话分布式系统
对于分布式系统的定义,大致可以理解为如下的两个点 分布式系统从整体的体量来说,它内部是由很多的服务器、服务实例组成。所提供的用户服务是由一组相互独立运行的服务器来提供。对于用户来说,这个多服务器的系统就跟一个服务器一样,感觉不到每个单独的服务器实例的存在。从…...
C++ 中 vector 的常用功能介绍
在 C 中,vector 是一种常用的动态数组容器,提供了方便的自动扩展、内存管理以及各种便捷的操作方法。它是 C 标准模板库(STL)的一部分,适用于需要动态存储和管理大量元素的场景。 在本文中,我们将简要介绍…...

[QT] QT事件与事件重写
一.事件 事件(event)是由系统或者 Qt本身在不同的场景下发出的。当用户按下鼠标、敲下键盘,或者是窗口关闭等都会发出一个相应的事件。 一些事件在用户操作时发出(如鼠标/键盘事件); 另一些事件则是由系统自动发出(如计时器事件)。 Qt窗口中对于产生的一系列事件都…...

c# 视觉识别图片文字 二维码
1.二维码识别 插件 ZXing.Net using System; using System.Drawing; // 如果你使用的是System.Drawing.Common using ZXing;class Program {static void Main(){string imagePath "path_to_your_qr_code_image.png";var barcodeBitmap (Bitmap)Image.FromFile(im…...

UEFI——访问PCI/PCIE设备(二)
一、支持访问PCI/PCIE设备的Protocol UEFI中提供了两个主要的模块来支持PCI总线,一是PCI Host Bridge(PCI主桥)控制器驱动,另一个是PCI总线驱动。这两个模块是和特定的平台硬件绑定的,在这种机制下,屏蔽了…...

决策树算法的介绍与应用
目录 引言 决策树算法的基本原理 表格总结:决策树的构建步骤 决策树算法的 MATLAB 实现 示例:使用决策树进行分类预测 决策树的应用场景 表格总结:决策树的主要应用领域 决策树的优势与局限 结论 引言 决策树是一种广泛应用于数据挖掘…...

杰发科技Bootloader(3)—— 基于7801的APP切到Boot
为了方便在APP中跳转到Boot重新进行升级,有两种办法,7840同样可以使用。 1. 调用reset接口进行复位,复位后会先进Boot,再自动跳转到App。 NVIC_SystemReset(); 2. 直接使用跳转指令,参考Boot跳转到App代码࿰…...

Leetcode面试经典150题-138.随机链表的复制
题目比较简单,重点是理解思想,random不管,copy一定要放在next 而且里面的遍历过程不能省略 解法都在代码里,不懂就留言或者私信 /* // Definition for a Node. class Node {int val;Node next;Node random;public Node(int val…...
freemarker模板学习笔记
文章目录 freemarker常用指令if-elseif-else指令switch, case, default, break指令list, else, items, sep, break 指令<#list>指令语法<#else> 指令<#items> 指令<#sep> 指令<#break> 指令 include 指令<#include> 基础知识<#include&…...
高亚科技与广东海悟携手,打造全流程电子竞标管理平台!
近日,中国企业管理软件资深服务商高亚科技与广东海悟科技有限公司(以下简称“海悟”)正式签署合作协议,双方将基于高亚科技的8Manage SRM系统,推进海悟采购管理的数字化升级,实现全流程在线电子竞标管理&am…...

240908-结合DBGPT与Ollama实现RAG本地知识检索增强
A. 最终效果 B. 背景说明 DBGPT在0.5.6版本中开始支持Ollama:v0.5.6 版本更新 网友对其Web端及界面端的设置进行了分享: feat(model): support ollama as an optional llm & embedding proxy by GITHUBear Pull Request #1475 eosphoros-ai/DB-G…...
AMD ThinkSystem服务器上的 Linux 和 C 状态设置 - Lenovo ThinkSystem
受影响的配置 该系统可以是以下任何Lenovo服务器: ThinkSystem 、SR645( ThinkSystem )ThinkSystem ,SR645 V3( ThinkSystem )ThinkSystem ,SR635 V3( ThinkSystem )Th…...
Redis过期删除和缓存淘汰
1. 过期删除 在 Redis 中,键的过期删除机制主要包括惰性删除(Lazy Deletion)和定期删除(Periodic Deletion)。这两种策略有各自的优缺点,Redis 最终会结合这两种方法来管理过期键。 1.1 惰性删除…...
React hook之useRef
React useRef 详解 useRef 是 React 提供的一个 Hook,用于在函数组件中创建可变的引用对象。它在 React 开发中有多种重要用途,下面我将全面详细地介绍它的特性和用法。 基本概念 1. 创建 ref const refContainer useRef(initialValue);initialValu…...

盘古信息PCB行业解决方案:以全域场景重构,激活智造新未来
一、破局:PCB行业的时代之问 在数字经济蓬勃发展的浪潮中,PCB(印制电路板)作为 “电子产品之母”,其重要性愈发凸显。随着 5G、人工智能等新兴技术的加速渗透,PCB行业面临着前所未有的挑战与机遇。产品迭代…...

Unity3D中Gfx.WaitForPresent优化方案
前言 在Unity中,Gfx.WaitForPresent占用CPU过高通常表示主线程在等待GPU完成渲染(即CPU被阻塞),这表明存在GPU瓶颈或垂直同步/帧率设置问题。以下是系统的优化方案: 对惹,这里有一个游戏开发交流小组&…...

React第五十七节 Router中RouterProvider使用详解及注意事项
前言 在 React Router v6.4 中,RouterProvider 是一个核心组件,用于提供基于数据路由(data routers)的新型路由方案。 它替代了传统的 <BrowserRouter>,支持更强大的数据加载和操作功能(如 loader 和…...

遍历 Map 类型集合的方法汇总
1 方法一 先用方法 keySet() 获取集合中的所有键。再通过 gey(key) 方法用对应键获取值 import java.util.HashMap; import java.util.Set;public class Test {public static void main(String[] args) {HashMap hashMap new HashMap();hashMap.put("语文",99);has…...

8k长序列建模,蛋白质语言模型Prot42仅利用目标蛋白序列即可生成高亲和力结合剂
蛋白质结合剂(如抗体、抑制肽)在疾病诊断、成像分析及靶向药物递送等关键场景中发挥着不可替代的作用。传统上,高特异性蛋白质结合剂的开发高度依赖噬菌体展示、定向进化等实验技术,但这类方法普遍面临资源消耗巨大、研发周期冗长…...

[ICLR 2022]How Much Can CLIP Benefit Vision-and-Language Tasks?
论文网址:pdf 英文是纯手打的!论文原文的summarizing and paraphrasing。可能会出现难以避免的拼写错误和语法错误,若有发现欢迎评论指正!文章偏向于笔记,谨慎食用 目录 1. 心得 2. 论文逐段精读 2.1. Abstract 2…...

【2025年】解决Burpsuite抓不到https包的问题
环境:windows11 burpsuite:2025.5 在抓取https网站时,burpsuite抓取不到https数据包,只显示: 解决该问题只需如下三个步骤: 1、浏览器中访问 http://burp 2、下载 CA certificate 证书 3、在设置--隐私与安全--…...
AI编程--插件对比分析:CodeRider、GitHub Copilot及其他
AI编程插件对比分析:CodeRider、GitHub Copilot及其他 随着人工智能技术的快速发展,AI编程插件已成为提升开发者生产力的重要工具。CodeRider和GitHub Copilot作为市场上的领先者,分别以其独特的特性和生态系统吸引了大量开发者。本文将从功…...

IoT/HCIP实验-3/LiteOS操作系统内核实验(任务、内存、信号量、CMSIS..)
文章目录 概述HelloWorld 工程C/C配置编译器主配置Makefile脚本烧录器主配置运行结果程序调用栈 任务管理实验实验结果osal 系统适配层osal_task_create 其他实验实验源码内存管理实验互斥锁实验信号量实验 CMISIS接口实验还是得JlINKCMSIS 简介LiteOS->CMSIS任务间消息交互…...