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

字符串的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. 原由 紧接上文&#xff0c;我们知道了暴力匹配的算法在时间运行上的缺陷&#xff0c;假设字符串T的长度为n&#xff0c;字符串P的长度为m&#xff0c;则整个算法的时间复杂度为O( n * m )&#xff0c;而对于一个复杂的现实情况而言 n >> m >> 2 &#xff08;即…...

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 模型&#xff0c;提升 CV 任务的性能 —— ImageNet 的 CNN 模型 NLP: BERT 简化了 NLP 任务的训练&#xff0c;提升了 NLP 任务的性能 BERT 如何站在巨人的肩膀上的&#xff1f;使用了哪些 NLP 已有的技术和思想&#xff…...

在Flask中实现跨域请求(CORS)

在Flask中实现跨域请求&#xff08;CORS&#xff0c;Cross-Origin Resource Sharing&#xff09;主要涉及到对Flask应用的配置&#xff0c;以允许来自不同源的请求访问服务器上的资源。以下是在Flask中实现CORS的详细步骤和方法&#xff1a; 一、理解CORS CORS是一种机制&…...

在桌面商业分析应用程序中启用高级 Web UI

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

CentOS Stream 8 通过 Packstack 安装开源 OpenStack(V版)

1、环境规划以及网卡配置 controller IP&#xff1a;192.168.235.101 compute IP&#xff1a;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 命令&#xff1a; -in <file>&#xff1a;指定输入文件。-out <file>&#xff1a;指定输出文件。-noout&#xff1a;不输出证书信息。-text&#xff1a;以文本格式输出证书信息。-pubke…...

架构师白话分布式系统

对于分布式系统的定义,大致可以理解为如下的两个点 分布式系统从整体的体量来说,它内部是由很多的服务器、服务实例组成。所提供的用户服务是由一组相互独立运行的服务器来提供。对于用户来说,这个多服务器的系统就跟一个服务器一样,感觉不到每个单独的服务器实例的存在。从…...

C++ 中 vector 的常用功能介绍

在 C 中&#xff0c;vector 是一种常用的动态数组容器&#xff0c;提供了方便的自动扩展、内存管理以及各种便捷的操作方法。它是 C 标准模板库&#xff08;STL&#xff09;的一部分&#xff0c;适用于需要动态存储和管理大量元素的场景。 在本文中&#xff0c;我们将简要介绍…...

[QT] QT事件与事件重写

一.事件 事件(event)是由系统或者 Qt本身在不同的场景下发出的。当用户按下鼠标、敲下键盘&#xff0c;或者是窗口关闭等都会发出一个相应的事件。 一些事件在用户操作时发出(如鼠标/键盘事件); 另一些事件则是由系统自动发出(如计时器事件)。 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总线&#xff0c;一是PCI Host Bridge&#xff08;PCI主桥&#xff09;控制器驱动&#xff0c;另一个是PCI总线驱动。这两个模块是和特定的平台硬件绑定的&#xff0c;在这种机制下&#xff0c;屏蔽了…...

决策树算法的介绍与应用

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

杰发科技Bootloader(3)—— 基于7801的APP切到Boot

为了方便在APP中跳转到Boot重新进行升级&#xff0c;有两种办法&#xff0c;7840同样可以使用。 1. 调用reset接口进行复位&#xff0c;复位后会先进Boot&#xff0c;再自动跳转到App。 NVIC_SystemReset(); 2. 直接使用跳转指令&#xff0c;参考Boot跳转到App代码&#xff0…...

Leetcode面试经典150题-138.随机链表的复制

题目比较简单&#xff0c;重点是理解思想&#xff0c;random不管&#xff0c;copy一定要放在next 而且里面的遍历过程不能省略 解法都在代码里&#xff0c;不懂就留言或者私信 /* // 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&…...

高亚科技与广东海悟携手,打造全流程电子竞标管理平台!

近日&#xff0c;中国企业管理软件资深服务商高亚科技与广东海悟科技有限公司&#xff08;以下简称“海悟”&#xff09;正式签署合作协议&#xff0c;双方将基于高亚科技的8Manage SRM系统&#xff0c;推进海悟采购管理的数字化升级&#xff0c;实现全流程在线电子竞标管理&am…...

240908-结合DBGPT与Ollama实现RAG本地知识检索增强

A. 最终效果 B. 背景说明 DBGPT在0.5.6版本中开始支持Ollama&#xff1a;v0.5.6 版本更新 网友对其Web端及界面端的设置进行了分享&#xff1a; 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服务器&#xff1a; ThinkSystem 、SR645&#xff08; ThinkSystem &#xff09;ThinkSystem &#xff0c;SR645 V3&#xff08; ThinkSystem &#xff09;ThinkSystem &#xff0c;SR635 V3&#xff08; ThinkSystem &#xff09;Th…...

Redis过期删除和缓存淘汰

1. 过期删除 在 Redis 中&#xff0c;键的过期删除机制主要包括惰性删除&#xff08;Lazy Deletion&#xff09;和定期删除&#xff08;Periodic Deletion&#xff09;。这两种策略有各自的优缺点&#xff0c;Redis 最终会结合这两种方法来管理过期键。 1.1 惰性删除&#xf…...

React hook之useRef

React useRef 详解 useRef 是 React 提供的一个 Hook&#xff0c;用于在函数组件中创建可变的引用对象。它在 React 开发中有多种重要用途&#xff0c;下面我将全面详细地介绍它的特性和用法。 基本概念 1. 创建 ref const refContainer useRef(initialValue);initialValu…...

盘古信息PCB行业解决方案:以全域场景重构,激活智造新未来

一、破局&#xff1a;PCB行业的时代之问 在数字经济蓬勃发展的浪潮中&#xff0c;PCB&#xff08;印制电路板&#xff09;作为 “电子产品之母”&#xff0c;其重要性愈发凸显。随着 5G、人工智能等新兴技术的加速渗透&#xff0c;PCB行业面临着前所未有的挑战与机遇。产品迭代…...

Unity3D中Gfx.WaitForPresent优化方案

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

React第五十七节 Router中RouterProvider使用详解及注意事项

前言 在 React Router v6.4 中&#xff0c;RouterProvider 是一个核心组件&#xff0c;用于提供基于数据路由&#xff08;data routers&#xff09;的新型路由方案。 它替代了传统的 <BrowserRouter>&#xff0c;支持更强大的数据加载和操作功能&#xff08;如 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仅利用目标蛋白序列即可生成高亲和力结合剂

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

[ICLR 2022]How Much Can CLIP Benefit Vision-and-Language Tasks?

论文网址&#xff1a;pdf 英文是纯手打的&#xff01;论文原文的summarizing and paraphrasing。可能会出现难以避免的拼写错误和语法错误&#xff0c;若有发现欢迎评论指正&#xff01;文章偏向于笔记&#xff0c;谨慎食用 目录 1. 心得 2. 论文逐段精读 2.1. Abstract 2…...

【2025年】解决Burpsuite抓不到https包的问题

环境&#xff1a;windows11 burpsuite:2025.5 在抓取https网站时&#xff0c;burpsuite抓取不到https数据包&#xff0c;只显示&#xff1a; 解决该问题只需如下三个步骤&#xff1a; 1、浏览器中访问 http://burp 2、下载 CA certificate 证书 3、在设置--隐私与安全--…...

AI编程--插件对比分析:CodeRider、GitHub Copilot及其他

AI编程插件对比分析&#xff1a;CodeRider、GitHub Copilot及其他 随着人工智能技术的快速发展&#xff0c;AI编程插件已成为提升开发者生产力的重要工具。CodeRider和GitHub Copilot作为市场上的领先者&#xff0c;分别以其独特的特性和生态系统吸引了大量开发者。本文将从功…...

IoT/HCIP实验-3/LiteOS操作系统内核实验(任务、内存、信号量、CMSIS..)

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