字符串的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 惰性删除…...
网络编程(Modbus进阶)
思维导图 Modbus RTU(先学一点理论) 概念 Modbus RTU 是工业自动化领域 最广泛应用的串行通信协议,由 Modicon 公司(现施耐德电气)于 1979 年推出。它以 高效率、强健性、易实现的特点成为工业控制系统的通信标准。 包…...
多云管理“拦路虎”:深入解析网络互联、身份同步与成本可视化的技术复杂度
一、引言:多云环境的技术复杂性本质 企业采用多云策略已从技术选型升维至生存刚需。当业务系统分散部署在多个云平台时,基础设施的技术债呈现指数级积累。网络连接、身份认证、成本管理这三大核心挑战相互嵌套:跨云网络构建数据…...
MySQL中【正则表达式】用法
MySQL 中正则表达式通过 REGEXP 或 RLIKE 操作符实现(两者等价),用于在 WHERE 子句中进行复杂的字符串模式匹配。以下是核心用法和示例: 一、基础语法 SELECT column_name FROM table_name WHERE column_name REGEXP pattern; …...
全面解析各类VPN技术:GRE、IPsec、L2TP、SSL与MPLS VPN对比
目录 引言 VPN技术概述 GRE VPN 3.1 GRE封装结构 3.2 GRE的应用场景 GRE over IPsec 4.1 GRE over IPsec封装结构 4.2 为什么使用GRE over IPsec? IPsec VPN 5.1 IPsec传输模式(Transport Mode) 5.2 IPsec隧道模式(Tunne…...
【开发技术】.Net使用FFmpeg视频特定帧上绘制内容
目录 一、目的 二、解决方案 2.1 什么是FFmpeg 2.2 FFmpeg主要功能 2.3 使用Xabe.FFmpeg调用FFmpeg功能 2.4 使用 FFmpeg 的 drawbox 滤镜来绘制 ROI 三、总结 一、目的 当前市场上有很多目标检测智能识别的相关算法,当前调用一个医疗行业的AI识别算法后返回…...
SQL慢可能是触发了ring buffer
简介 最近在进行 postgresql 性能排查的时候,发现 PG 在某一个时间并行执行的 SQL 变得特别慢。最后通过监控监观察到并行发起得时间 buffers_alloc 就急速上升,且低水位伴随在整个慢 SQL,一直是 buferIO 的等待事件,此时也没有其他会话的争抢。SQL 虽然不是高效 SQL ,但…...
MySQL:分区的基本使用
目录 一、什么是分区二、有什么作用三、分类四、创建分区五、删除分区 一、什么是分区 MySQL 分区(Partitioning)是一种将单张表的数据逻辑上拆分成多个物理部分的技术。这些物理部分(分区)可以独立存储、管理和优化,…...
android RelativeLayout布局
<?xml version"1.0" encoding"utf-8"?> <RelativeLayout xmlns:android"http://schemas.android.com/apk/res/android"android:layout_width"match_parent"android:layout_height"match_parent"android:gravity&…...
Vue 模板语句的数据来源
🧩 Vue 模板语句的数据来源:全方位解析 Vue 模板(<template> 部分)中的表达式、指令绑定(如 v-bind, v-on)和插值({{ }})都在一个特定的作用域内求值。这个作用域由当前 组件…...
DBLP数据库是什么?
DBLP(Digital Bibliography & Library Project)Computer Science Bibliography是全球著名的计算机科学出版物的开放书目数据库。DBLP所收录的期刊和会议论文质量较高,数据库文献更新速度很快,很好地反映了国际计算机科学学术研…...
