【数据结构】KMP
迪丽瓦拉
2025-06-01 18:00:59
0次

目录

一：简介

二：实现

三：next数组的解释

四：优化

一：简介

 KMP算法是一种字符串匹配算法，可以在 O(n+m)的时间复杂度内实现两个字符串的匹配。
所谓字符串匹配，是这样一种问题：“字符串 P 是否为字符串 S 的子串？如果是，它出现在 S 的哪些位置？” 其中 S 称为主串；P称为模式串。

 

如果暴力就是O（n*m），两个for循环，ij同时动。

二：实现

 

#include 
using namespace std;#define MAXLEN 225typedef struct
{char ch[MAXLEN];int length;
} String;void get_next(String T,int next[])
{int i=1,j=0; //i领先一个位置next[1]=0;while(iT.length) return i-T.length; //不需要+1,因为while1循环退出之前i++,用来while循环判断了else return 0;
}int main()
{String s1,s2; //s1母串,s2子串char a[MAXLEN],b[MAXLEN];cout<<"输入母串:"<>s1.ch+1;s1.length=strlen(s1.ch)-1;cout<<"输入子串:"<>s2.ch+1;s2.length=strlen(s2.ch)-1;int next[MAXLEN];get_next(s2,next);cout<<"next数组如下"<

三：next数组的解释

  1.  j是短字符串的指针，i是长字符串；
  2. next数组只看短字符串，next[j]=1到j-1的最长前后相等缀+1；
  3. 默认next[1]=0;next[2]=1；

如下图：j=4,j前面即j-1到1的子串为aba，最长前后相等缀为a即1，next[4]=1+1=2

               j=6,j前面即j-1到1的子串为abaab，最长前后相等缀为ab即2，next[6]=2+1=3

四：优化

puls优化nextval[j]数组:

        当已经出现过一个字母时，eg：a，则令nextval[3]=next[1]=0

                                                    eg：b，则令nextval[4]=next[2]=1 

        j指针就不用重复遍历已出现的a、b了

这里写的是直接改好的val数组

#include 
using namespace std;#define MAXLEN 225typedef struct
{char ch[MAXLEN];int length;
} String;int  Index_KMP(String S,String T,int next[])
{int i=1,j=1;while(i<=S.length&&j<=T.length){if(j==0||S.ch[i]==T.ch[j]){i++,j++;//匹配成功,i和j向后移动}else{j=next[j];//j回调可以直接匹配的位置}}if(j>T.length) return i-T.length; //不需要+1,因为while1循环退出之前i++,用来while循环判断了else return 0;
}void get_nextval(String T,int nextval[])
{int i=1,j=0;while(i>s1.ch+1;s1.length=strlen(s1.ch)-1;cout<<"输入子串:"<>s2.ch+1;s2.length=strlen(s2.ch)-1;int next[MAXLEN];get_nextval(s2,next);cout<<"nextval数组如下"<

 

动画演示

词库加载错误:未能找到文件“E:\highferrum_mysql\Configuration\Dict_Stopwords.txt”。

上一篇：JVM内存模型简介

下一篇：计算机网络（三）网络协议栈与epoll的底层原理

相关内容

热门资讯

linux入门---制作进度条 了解缓冲区 我们首先来看看下面的操作： 我们首先创建了一个文件并在这个文件里面添加了...
C++ 机房预约系统（六）：学... 8、 学生模块 8.1 学生子菜单、登录和注销 实现步骤： 在Student.cpp的...
A.机器学习入门算法（三）：基... 机器学习算法（三）：K近邻(k-nearest neigh...
数字温湿度传感器DHT11模块... 模块实例https://blog.csdn.net/qq_38393591/article/deta...
有限元三角形单元的等效节点力 文章目录前言一、重新复习一下有限元三角形单元的理论1、三角形单元的形函数（Nÿ...
Redis 所有支持的数据结构... Redis 是一种开源的基于键值对存储的 NoSQL 数据库，支持多种数据结构。以下是...
win下pytorch安装—c... 安装目录一、cuda安装1.1、cuda版本选择1.2、下载安装二、cudnn安装三、pytorch...
MySQL基础-多表查询 文章目录MySQL基础-多表查询一、案例及引入1、基础概念2、笛卡尔积的理解二、多表查询的分类1、等...
keil调试专题篇 调试的前提是需要连接调试器比如STLINK。 然后点击菜单或者快捷图标均可进入调试模式。 如果前面...
MATLAB | 全网最详细网... 一篇超超超长，超超超全面网络图绘制教程，本篇基本能讲清楚所有绘制要点&#...
IHome主页 - 让你的浏览... 随着互联网的发展，人们越来越离不开浏览器了。每天上班、学习、娱乐，浏览器...
TCP 协议 一、TCP 协议概念 TCP即传输控制协议（Transmission Control ...
营业执照的经营范围有哪些 营业执照的经营范围有哪些 经营范围是指企业可以从事的生产经营与服务项目，是进行公司注册...
C++ 可变体(variant... 一、可变体(variant) 基础用法 Union的问题： 无法知道当前使用的类型是什...
血压计语音芯片，电子医疗设备声... 语音电子血压计是带有语音提示功能的电子血压计，测量前至测量结果全程语音播报࿰...
MySQL OCP888题解0... 文章目录1、原题1.1、英文原题1.2、答案2、题目解析2.1、题干解析2.2、选项解析3、知识点3...
【2023-Pytorch-检... （肆十二想说的一些话）Yolo这个系列我们已经更新了大概一年的时间，现在基本的流程也走走通了，包含数...
实战项目：保险行业用户分类 这里写目录标题1、项目介绍1.1 行业背景1.2 数据介绍2、代码实现导入数据探索数据处理列标签名异...
记录--我在前端干工地(thr... 这里给大家分享我在网上总结出来的一些知识，希望对大家有所帮助 前段时间接触了Th...
43 openEuler搭建A... 文章目录43 openEuler搭建Apache服务器-配置文件说明和管理模块43.1 配置文件说明...