数据结构面试常见问题之串的模式匹配(KMP算法)系列-大师改进实现以及原理

😀前言
KMP算法是一种改进的字符串匹配算法,由D.E.Knuth,J.H.Morris和V.R.Pratt提出的,因此人们称它为克努特—莫里斯—普拉特操作(简称KMP算法)。KMP算法的核心是利用匹配失败后的信息,尽量减少模式串与主串的匹配次数以达到快速匹配的目的。

🏠个人主页:尘觉主页

文章目录

  • 数据结构面试常见问题之串的模式匹配(KMP算法)系列-大师改进实现以及原理
    • KMP-3. KMP 算法实现
      • KMP算法实现
    • KMP-4. BuildMatch 的实现原理
    • KMP-5. BuildMatch的编程实现
    • 😄总结

数据结构面试常见问题之串的模式匹配(KMP算法)系列-大师改进实现以及原理

KMP-3. KMP 算法实现

#include<stdio.h>
#include<string.h>
typedef int Position;//Position对应的是一个整型变量,指的是数组的下标
#define NotFound -1//NotFound就应该定义成一个不可能是数组下标的东西
int main()
{char string[] = "This is a simple example.";//默认指字符串,但这个串可以是任何类型的char pattern[] = "simple";Position p = KMP(string,pattern);//返回的是一个字符指针的话就只能处理字符串,如果返回的是数组下标的话那可以处理任何字符的串if (p == NotFound ) printf("Not Found.\n");else printf("%s\n",string+p);//因为这里返回的是整数,这个整数就没办法被当作字符串的头指针了。如果我们要打印整个字符串的话,我们这里就只能写成string+p这样的形式return 0;
}

KMP算法实现

在这里插入图片描述
一直走到指针不匹配
在这里插入图片描述


Position KMP(char *string, char *pattern) {int n = strlen(string);//strlen得到string的长度,下方也是一样 复杂度:O(n)int m = strlen(pattern);//复杂度:O(m)int s, p,*match;//声明两个指针if (n < m) return NotFound;//找的n不可能比m短match = (int *) malloc(sizeof(int) * m);BuildMatch(pattern, match);//Tm = O(?)s = p = 0;while (s < n && p < m) { //当这两个指针一起往前飞,任何一个指针先指到自己指的串的末尾的时候结束,复杂度O(n)if (string[s] == pattern[p]) {s++;p++;}//p有时候加加有时候回退,但s永远加加else if (p > 0) p = match[p - 1] + 1;//为了防止得到段错误,这里加上条件p>0//如果p = 0的话,意味着pattern从第一个字符就不匹配,这个时候p不动,s向前走一格else s++;//当string[s] == pattern[p]不匹配,我们s++,继续下一轮匹配}//在我们跳出while循环的时候,p指针已经碰到pattern的末尾(p==m),那就是完全的匹配上了//反之p还没有到结尾,而string已经到p的结尾了,就意味着我们找不到这个模式return (p == m) ? (s - m) : NotFound;
}

在这里插入图片描述
KMP的整体时间复杂度:T = O(n+m+Tm)

KMP-4. BuildMatch 的实现原理

在这里插入图片描述
如果采用这种方法实现的话,时间复杂度将会达到Tm = O(m³)

新想法:如果我们要算j的match值的话先考虑他跟j-1的match值有什么关系

假如我们这是从0到j-1的字段

在这里插入图片描述

match[j] >= match[j-1] + 1(是否正确?)

如果 match[j-1]+1 这个位置上的字符与 j 位置上的字符相等,match[j] 会有可能比 match[j-1]+1 更大吗?没可能
在这里插入图片描述

match[j] = match[j-1] + 1 (最多持平啦,利用反证法证明)
且能得到这个结果的前提是运行很好在这里插入图片描述

当 pattern[match[j-1]+1] != pattern[j] 时,下一个待与 pattern[j] 比较的元素下标是:match[match[j-1]]+1
在这里插入图片描述

KMP-5. BuildMatch的编程实现

void BuildMatch(char *pattern,int *match)
{int i,j;int m = strlen(pattern);//复杂度O(m)match[0] = -1;for(j=1;j<m;j++){//复杂度O(m)i = match[j-1];//把这个值存入i里面,后面就可以直接用i来表示,不至于显得很长很啰嗦,怎么感觉像数学的换元法啊哈哈while((i>=0) && (pattern[i+1] != pattern[j]))//每次都考虑最坏情况的话复杂度可能就为O(j)了,每次都退到底的话i = match[i];//让i做了一个回退,回退到while条件两者有其中之一不发生的时候if(pattern[i+1]==pattern[j])match[j] = i+1;//i回退总次数不会超过i增加的总次数else match[j] = -1;}
}

整个算法复杂度:在这里插入图片描述
第一篇–>数据结构面试常见问题之串的模式匹配(KMP算法)系列-简单解决方案

第二篇–>数据结构面试常见问题之串的模式匹配(KMP算法)系列-大师改进

😄总结

KMP算法的核心思想是利用部分匹配表来记录模式串中每个字符之前部分匹配的最大长度。在匹配过程中,如果主串和模式串的某个字符不匹配,则可以根据部分匹配表直接跳转到模式串中下一个可能匹配的位置,从而避免重复比较。

BuildMatch函数用于计算模式串的部分匹配表。该函数的核心思想是利用前缀和后缀的匹配关系来计算部分匹配表。

KMP算法具有广泛的应用,例如文本编辑、生物信息学、数据挖掘等。

😁热门专栏推荐
想学习vue的可以看看这个

java基础合集

数据库合集

redis合集

nginx合集

linux合集

手写机制

微服务组件

spring_尘觉

springMVC

mybits

等等等还有许多优秀的合集在主页等着大家的光顾感谢大家的支持

🤔欢迎大家加入我的社区 尘觉社区

文章到这里就结束了,如果有什么疑问的地方请指出,诸佬们一起来评论区一起讨论😁
希望能和诸佬们一起努力,今后我们一起观看感谢您的阅读🍻
如果帮助到您不妨3连支持一下,创造不易您们的支持是我的动力🤞

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/284819.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

Jackson 2.x 系列【2】生成器 JsonGenerator

有道无术&#xff0c;术尚可求&#xff0c;有术无道&#xff0c;止于术。 本系列Jackson 版本 2.17.0 源码地址&#xff1a;https://gitee.com/pearl-organization/study-seata-demo 文章目录 1. 前言2. 案例演示2.1 创建 JsonFactory2.2 创建 JsonGenerator2.3 写入操作2.4 查…

stm32使用定时器实现PWM与呼吸灯

PWM介绍 STM32F103C8T6 PWM 资源&#xff1a; 高级定时器&#xff08; TIM1 &#xff09;&#xff1a; 7 路 通用定时器&#xff08; TIM2~TIM4 &#xff09;&#xff1a;各 4 路 例如定时器2 PWM 输出模式&#xff1a; PWM 模式 1 &#xff1a;在 向上计数 时&#xff0…

GETSHELL方法总结上

渗透的总步骤 1.信息收集找到弱漏洞 2.漏洞挖掘 漏洞验证 3.有一定权限 getshell 4.提权后---渗透 5.内网渗透】 前后台拿shell方法汇总 接下来我们实操一波dedecms也就是织梦cms 如果你们的靶场是空白的 可能是php版本 我们修改为5.2 可能是源码问题 我们不要急着上传…

c++常考基础知识(2)

二.c关键字 关键字汇总 c中共有63个关键字&#xff0c;其中包括int&#xff0c;char&#xff0c;double等类型关键字&#xff0c;if&#xff0c;else&#xff0c;while&#xff0c;do&#xff0c;等语法关键字&#xff0c;还有sizeof等函数关键字。 三.数据结构 1.数组&#x…

【算法】小强爱数学(迭代公式+数论取模)

文章目录 1. 问题2. 输入3. 输出4. 示例5. 分析6. 思路7. 数论&#xff0c;取模相关公式8. 数论&#xff0c;同余定理9. 代码 1. 问题 小强发现当已知 x y B xyB xyB以及 x y A xyA xyA时,能很轻易的算出 x n x_ {n} xn​ y n y_ {n} yn​ 的值.但小强想请你在已知A和B的…

数据结构(五)——树森林

5.4 树和森林 5.4.1 树的存储结构 树的存储1&#xff1a;双亲表示法 用数组顺序存储各结点&#xff0c;每个结点中保存数据元素、指向双亲结点(父结点)的“指针” #define MAX_TREE_SIZE 100// 树的结点 typedef struct{ElemType data;int parent; }PTNode;// 树的类型 type…

【Mysql】硬盘性能压测(Sysbench工具)

1、IOPS和吞吐量介绍 IOPS&#xff08;每秒输入/输出操作数&#xff09;&#xff1a;是衡量存储设备每秒能够执行的输入/输出操作的数量。对于数据库等需要频繁读写的应用程序而言&#xff0c;IOPS 是一个关键的性能指标。更高的 IOPS 意味着存储设备能够处理更多的读写请求&am…

【Vue】三、使用ElementUI实现图片上传

目录 一、前端代码实现 二、后端代码实现 三、调试效果实现 一、前端代码实现 废话不多说直接上代码 <el-form-item prop"image" label"上传图片" v-model"form.image"><el-upload:action"http://localhost:8…

基于springboot+vue的智慧生活商城系统

博主主页&#xff1a;猫头鹰源码 博主简介&#xff1a;Java领域优质创作者、CSDN博客专家、阿里云专家博主、公司架构师、全网粉丝5万、专注Java技术领域和毕业设计项目实战&#xff0c;欢迎高校老师\讲师\同行交流合作 ​主要内容&#xff1a;毕业设计(Javaweb项目|小程序|Pyt…

Stable Diffusion 本地训练端口与云端训练端口冲突解决办法

方法之一&#xff0c;修改本地训练所用的端口 1 首先&#xff0c;进入脚本训练器的根目录 例如&#xff1a;C:\MarkDeng\lora-scripts-v1.7.3 找到gui.py 2 修改端口号 因为云端训练器也是占用28000和6006端口 那么本地改成27999和6007也是可以的 保存退出&#xff0c;运行启动…

如何在C语言中使用命令行参数

C语言文章更新目录 C语言学习资源汇总&#xff0c;史上最全面总结&#xff0c;没有之一 C/C学习资源&#xff08;百度云盘链接&#xff09; 计算机二级资料&#xff08;过级专用&#xff09; C语言学习路线&#xff08;从入门到实战&#xff09; 编写C语言程序的7个步骤和编程…

【C++】关联式容器——map和set

1 关联式容器 STL中我们常用的部分容器&#xff0c;比如&#xff1a;vector、list、deque、forward_list(C11)等&#xff0c;这些容器统称为序列式容器&#xff0c;因为其底层为线性序列的数据结构&#xff0c;里面存储的是元素本身。 那什么是关联式容器呢&#xff1f;它与序…

阿里云服务器2核4G服务器收费价格表,1个月和一年报价

阿里云2核4G服务器多少钱一年&#xff1f;2核4G服务器1个月费用多少&#xff1f;2核4G服务器30元3个月、85元一年&#xff0c;轻量应用服务器2核4G4M带宽165元一年&#xff0c;企业用户2核4G5M带宽199元一年。本文阿里云服务器网整理的2核4G参加活动的主机是ECS经济型e实例和u1…

JAVA面向对象编程 JAVA语言入门基础

类与对象的概念 类 (Class) 和对象 (Object) 是面向对象程序设计方法中最核心的概念。 类是对某一类事物的描述(共性)&#xff0c;是抽象的、概念上的定义&#xff1b;而对象则是实际存在的属该类事物的具体的个体&#xff08;个性&#xff09;&#xff0c;因而也称为实例(In…

透视未来工厂:山海鲸可视化打造数字孪生新篇章

在信息化浪潮的推动下&#xff0c;数字孪生工厂项目正成为工业制造领域的新宠。作为一名山海鲸可视化的资深用户&#xff0c;我深感其强大的数据可视化能力和数字孪生技术在工厂管理中的应用价值&#xff0c;同时我们公司之前也和山海鲸可视化合作制作了一个智慧工厂项目&#…

学习或复习电路的game推荐:nandgame(NAND与非门游戏)、Turing_Complete(图灵完备)

https://www.nandgame.com/ 免费 https://store.steampowered.com/app/1444480/Turing_Complete/ 收费&#xff0c;70元。据说可以导出 Verilog &#xff01;

转座子插入位点分析4------PS转座子测序数据分析

观察数据 这是经公司使用fastp质控后的数据&#xff0c;我们先挑选部分数据进行比对&#xff0c;观察序列结构 为了准确性&#xff0c;我们再次挑选另一批数据进行比对 可以看到&#xff0c;所有序列都存在一个“GTGTCAAATACTTATTTTCCCCGCTGTA”的前导序列&#xff0c;这可能…

深度学习pytorch——多层感知机反向传播(持续更新)

在讲解多层感知机反向传播之前&#xff0c;先来回顾一下多输出感知机的问题&#xff0c;下图是一个多输出感知机模型&#xff1a; 课时44 反向传播算法-1_哔哩哔哩_bilibili 根据上一次的分析深度学习pytorch——感知机&#xff08;Perceptron&#xff09;&#xff08;持续更新…

突破边界:Web3开启数字化社会的新纪元

引言 随着科技的不断进步和数字化社会的发展&#xff0c;Web3正逐渐成为了人们关注的焦点。作为新一代互联网的演进形态&#xff0c;Web3具有突破传统边界、实现去中心化的特点&#xff0c;被认为将开启数字化社会的新纪元。本文将深入探讨Web3的概念、特点、应用场景&#xf…

Java 自定义线程池实现

自定义线程池 简介任务图示阻塞队列 BlockingQueue<T>ReentrantLock代码 线程池 ThreadPool工作线程类 Worker 拒绝策略接口代码测试类 TestThreadPool为什么需要j i&#xff1f;&#xff08;lambad表达式相关&#xff09; 测试结果拒绝策略&#xff1a;让调用者自己执行…