【C语言】KMP算法（详解）

目录

  • 1. 朴素的模式匹配
  • 2. KMP算法解决的问题
  • 3. KMP算法
    • 公共前后缀（重点）
    • next 数组
    • KMP算法实现

1. 朴素的模式匹配

  • 朴素算法中，当匹配到不同位时，主串指针i会退回到该次匹配起点处的下一位置，以其为下一次匹配的主串起点

  • 同时字串的j指针退回其起始位置

  • 如此一来每次匹配主串指针后移一位，字串指针始终在其起始位置

  • 时间复杂度为Om*n)

在这里插入图片描述

2. KMP算法解决的问题

  • 可以发现下图中，在第二次匹配时，第一个元素就已经不一样了

  • 朴素算法的缺点就在于其会傻傻的执行许多次这样不必要的判断

  • 这就是KMP算法所解决的问题

在这里插入图片描述

3. KMP算法

  • 主串指针不会进行回溯，不会回到朴素匹配中的下一匹配点
  • 利用已匹配部分中的公共前后缀来调整字串指针位置，以此加速下一次匹配

根据下面的动画感受感受
在这里插入图片描述

  • 可以看到，主串指针 i )在整个查找过程中都没有前移，每次查找的起点均为上次查找的结束点，即 i 永远不递减，这也使KMP的精髓
  • 同时，当不匹配位置前一位对应的next数组中元素不为0时，字串指针 j )会向后偏移相应个数的字符
  • 这样一来，无论是主串还是字串的判断次数都得到了优化，时间复杂度优化至Om+n)

公共前后缀（重点）

公共前后缀的计算：
这里用公式理解，计算下标为a处的公共前后缀个数，如果[a-x,a]范围的每一个元素与[0,x]范围的每一个元素相等，则a处的公共前后缀个数为x+1

在这里插入图片描述
 

这里注意找某一位置的公共前后缀时，要将起始位置的字符同该位置字符比较，而不是只要在该位置之前出现了相同元素就判断存在公共前后缀
如下图中的红色位置B，虽然在其之前存在一个字符B，但是该位置的公共前后缀为0

在这里插入图片描述

 
 
 

next 数组

理解了什么是公共前后缀，其实next数组就是存储该数组每个对应位置公共前后缀数量的数组
 

（这里的next数组实际上为PM表，PM表右移一位 空缺的用-1填充，最后一个元素的部分匹配值用于下一个元素，但没有下一个元素故可以舍弃) 并加一得到next数组。）
在这里插入图片描述
在这里插入图片描述
next表的含义是子串的第j个字符发生失配时跳到子串的next[j]位置重新与主串当前位置进行比较。

 

代码实现next数组（PM表）

int* get_nextconst char* p)
{assertp);int len = strlenp);int* next = int*)mallocsizeofint) * len);if next == NULL){return NULL;}else{//先将其全部初始化为0memsetnext, 0, sizeofint) * len);int j = 0;int i = 0;for i = 1; i < 6; i++){if p[i] == p[j]){next[i] = next[i - 1] + 1;j++;}else{j = 0;}}return next;}
}

 
 

KMP算法实现

注意代码注释

int my_kmpchar* a1, char* a2)
{int* next = get_nexta2);int len1 = strlena1);int len2 = strlena2);int i = 0;int j = 0;while i < len1){if a1[i] == a2[j]){i++;j++;}else if j > 0)  // j>0 时，根据next数组调整 j 的位置j = next[j - 1];else   //字串第一个字符就不匹配i++;if j == len2) //匹配成功，返回值为字串第一个字符在主串中的位置return i - j;}return -1;
}

查看全文

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

如若内容造成侵权/违法违规/事实不符，请联系一条长河网进行投诉反馈，一经查实，立即删除！

相关文章：

在这里插入图片描述

【C语言】KMP算法（详解）

目录1. 朴素的模式匹配2. KMP算法解决的问题3. KMP算法公共前后缀（重点）next 数组KMP算法实现1. 朴素的模式匹配 朴素算法中，当匹配到不同位时，主串指针i会退回到该次匹配起点处的下一位置，以其为下一次匹配的主串起点……

编程日记2023/3/15 20:44:18

linux trace point机制2–增加trace event

为fuse模块新增trace event，执行stat命令时，记录trace，输出inode的信息。
一、trace event定义
include\trace\events目录下新增fuse.h文件 /* SPDX-License-Identifier: GPL-2.0 */ #undef TRACE_SYSTEM /* 在/d/tracing（软链接……

编程日记2023/3/15 20:44:09

π-Day快乐：Python可视化π

π-Day快乐：Python可视化π
今天是3.14，正好是圆周率 π\piπ 的前3位，因此数学界将这一天定为π\bold{\pi}π day。 π\piπ 可能是最著名的无理数了，人类对 π\piπ 的研究从未停止。目前人类借助计算机已经计算到 π\piπ 小数……

编程日记2023/3/15 20:43:59

网络协议分析期末复习（一）

目录 1.因特网概述
2.TCP/IP分层模型相关内容
（1）OSI参考模型及TCP/IP参考模型
（2）各层定义
（3）层次间的数据格式
（4）TCP/IP两个边界的定义
3.大端点机和小端点机定义
4.PPP协……

编程日记2023/3/15 20:43:50

高等数学——二重积分

文章目录概念性质计算利用直角坐标计算利用极坐标计算利用函数的奇偶性计算利用变量的轮换对称性计算概念
定义：设函数zfx,y)zfx,y)zfx,y)在有界区域DDD上有定义，将区域DDD任意分成nnn个小区域Δσ1,Δσ2,…,Δσn\Delta\sigma_1,\Delta\sigma_2,.……

编程日记2023/3/15 20:43:41

ChatGPT的前世今生

作者🕵️‍♂️：让机器理解语言か 专栏🎇：NLP（自然语言处理） 描述🎨：让机器理解语言，让世界更加美好！ 寄语💓：🐾没有白走的……

编程日记2023/3/15 20:43:31

阅读文献克服这三大问题，效率绝对蹭蹭涨

文献阅读是做科研、写论文的重要基础，但是并非每一个科研人员都喜欢和擅长阅读文献，看着密密麻麻的文字资料，硬是一个字也看不进去。经小编总结发现，文献看不下去一般存在三个问题：坐不住，记不住&#xff0……

编程日记2023/3/15 20:43:29

做大数据不得不看的一篇分析—大图数据分析系统综述

现在互联网上涌现出了越来越多的应用，这些应用背后的数据结构日益复杂，已经超越了现有数据模型的表示能力。由于图数据模型的灵活性，越来越多的应用使用图数据模型来表示数据。
特别是近年来，随着社交网络与语义网的发展&#xf……

编程日记2023/3/15 20:43:29

2018年科研大事件——科学和伦理之间的较量

本文源于掌桥科研
01美国新型艾滋病疫苗证实有效，猴子注射后成功免疫
美国斯克里普斯研究所研发出一种新型艾滋病疫苗，在向72只恒河猴注射之后，三分之二猴子成功免疫与艾滋病毒相似的猴免疫缺陷病毒。科学家们已开始对非洲南部2600名有艾滋……

编程日记2023/3/15 20:43:28

谜一样的计算机科学之父，竟因同性恋致使职业生涯尽毁

本文来源：掌桥科研
20世纪后半段开始，电子计算机对人类文明产生了惊天动地的变革。随着计算机科学技术的不断发展，现如今计算机的种类繁多，应用领域也是非常广泛，主要应用领域有信息处理、科学计算、过程控制、计算机……

编程日记2023/3/15 20:43:28

【Linux基础】常用命令整理

ls命令
-a选项，可以展示隐藏的文件和文件夹-l选项，以列表形式展示内容-h，需要和-l搭配使用，可以展示文件的大小单位ls -lah等同于la -a -l -h
cd命令（change directory）
语法：cd [Linux路径]……

编程日记2023/4/16 14:51:26

客快物流大数据项目（一百一十二）：初识Spring Cloud

文章目录
初识Spring Cloud
一、Spring Cloud简介
二、SpringCloud 基础架构图…

编程日记2023/4/16 14:51:11

C和C++中的struct有什么区别

区别一： C语言中： Struct是用户自定义数据类型（UDT）。 C语言中： Struct是抽象数据类型（ADT），支持成员函数的定义。
区别二：
C中的struct是没有权限设置的&#xff0c……

编程日记2023/4/16 14:50:59

docker的数据卷详解

数据卷 数据卷是宿主机中的一个目录或文件，当容器目录和数据卷目录绑定后，对方修改会立即同步
一个数据卷可以同时被多个容器同时挂载，一个容器也可以被挂载多个数据卷
数据卷作用：容器数据持久化 /外部机器和容器间接通信 /容器……

编程日记2023/4/16 14:50:50

13、Qt生成dll-QLibrary方式使用

Qt创建dll，使用QLibrary类方式调用dll
一、创建项目
1、新建项目->其他项目->Empty qmake Project->Choose 2、输入项目名，选择项目位置，下一步 3、选择MinGW，下一步 4、完成 5、.pro中添加TEMPLATE subdirs&#xff……

编程日记2023/4/16 14:50:38

基于mapreduce 的 minHash 矩阵压缩

Minhash作用： 对大矩阵进行降维处理，在进行计算俩个用户之间的相似度。
比如： 俩个用户手机下载的APP的相似度，在一个矩阵中会有很多很多的用户要比较没俩个用户之间的相似度是一个很大的计算任务 如果首先对这个矩阵降维处理&am……

编程日记2023/4/16 14:50:37

关于hashmap使用迭代器的问题

keySet获得的只是key值的集合，valueSet获得的是value集合，entryset获得的是键值对的集合。 package com.test2.test;import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;
import java.util.Map.Entry;public class mapiterator……

编程日记2023/4/16 14:50:37

Hadoop入口FileSystem HDFS操作 本地文件合并到HDFS和HDFS文件合并

Hadoop 文件API的起点是FileSystem类。这是一个与文件系统交互的抽象类。存在不同的具体实现子类来处理HDFS和本地文件系统。
HDFS接口的FileSystem对象：
Configuration conf new Configuration);
FileSystem hdfs FileSystem.getconf); HDFS直接操作&#x……

编程日记2023/4/16 14:50:36

combiner partitioner

combine是在map端进行的，是在patition之后 partitioner也是在map端进行的 combine 适用在每个map端进行简单的合并，同样也是继承Reduce类。…

编程日记2023/4/16 14:50:35

toString.indexOf:)和subsTring

package com.test2.test;public class subStirngTest {public static void mainString[] args) {String sb"abcdefgh";String sc"abcd:efgh";int splitIndexsc.indexOf":");//找到标识符的位置System.out.printlnsplitIndex);sb.substring1)……

编程日记2023/4/16 14:50:35

Published by

风君子

独自遨游何稽首 揭天掀地慰生平