KPM匹配算法

article/2025/10/9 8:29:54

KPM匹配算法

  • 不管在工作中还是学习中经常会遇到串的模式匹配,一般来说,串的模式匹配算法主要是两种【朴素模式匹配和KPM模式匹配】+一种改良【KPM的改良】,下面先看一下朴素模式匹配:
  • 朴素模式匹配主要思想比较简单也比较粗暴,假设一个需要查找的目标串T和源串S,当我们进行匹配的时候,要设置一个滑动指针,从目标串T的第一个字符与源串S进行匹配,若相同则继续往右滑动,若是出现一个不同,则将滑动指针回溯到目标串的0位置,并将目标串T相对于源串右移一个字符,重新比较。直至滑动指针超过源串S长度【未找到】或者超过目标串T长度【找到】。
  • 我们用一个例子来说明一些这个算法:现在有主串S:ababcabcacbab,模式串T:abcac。我们来看一下是如何匹配的。i从0开始,j也从0开始。

在第一次匹配中,i从0开始,j从0开始。当i=2,j=2时匹配失败,此时i回溯到1,j回溯到0。
在这里插入图片描述

第二次匹配中,i从1开始,j从0开始。当i=1,j=0时匹配失败,此时i回溯到2,j回溯到0。
在这里插入图片描述

第三次匹配中,i从2开始,j从0开始。当i=6,j=4时匹配失败,此时i回溯到3,j回溯到0。
在这里插入图片描述

第四次匹配中,i从3开始,j从0开始。当i=3,j=0时匹配失败,此时i回溯到4,j回溯到0。
在这里插入图片描述

第五次匹配中,i从4开始,j从0开始。当i=4,j=0时匹配失败,此时i回溯到5,j回溯到0。
在这里插入图片描述

第六次匹配中,i从5开始,j从0开始。i=10,j=5,T中全部字符比较完,匹配成功,返回本次匹配起始位置下标i - j。(i=9和j=4的时候匹配成功,i和j会再加一次,所以i=10,j=5)
在这里插入图片描述

  • 从上面可以看出每次匹配出现不同就会回溯,大量时间浪费在回溯上面,我们可以的得出朴素匹配模式的时间复杂度为O((L(S)-L(T)+1)*L(T))【其中L()代表字串的长度,S为源串,T为目标串】

  • 下面着重介绍一下KMP算法:
    从上面例子的第一幅图我们可以看到,当T中的c与S的a出现不同的时候前面的b是相同的,我们明知道第一位的a与第二位的b是不相同的,那我们为什么还要往右移一位,再次比较呢,浪费了时间。KMP算法主要是减少了指针回溯的长度,它并不必须将指针回溯到初始位置,而是根据对目标串T计算出的某一位置与其前面子串的前缀与后缀的最大公共重复子串的前缀的子串的最大位置+1的关联数组next来决定位置的,可能比较绕,下面会来解释。我们先来拆分一下这句话的知识点:
    什么是前后缀最大公共重复子串呢?
    我们可以通过几个小例子来看一下:

  1. ababaaab:前缀:abbaaaab 后缀:ababaaab,重复的最大子串是ab
  2. ababa:前缀:ababa 后缀:ababa ,重复的最大子串是aba
  3. aaaa:前缀:aaaa 后缀:aaaa,重复的最大子串aaa,此处需要注意的:前后缀的最大子串不可与父串相同,否则没有意义。
    什么是前缀的子串的最大位置+1
    我们求出的前后缀的最大重复的公共子串,要分为前缀和后缀两部分,上部分的例子已经说明,而我们需要的是前缀的部分,例如:
  4. ababaaab:前缀:abbaaaab,这样我们取的位置就是 3,也就是长度+1,为什么我们需要这部分呢?这与KPM算法的执行过程有关,下面再重点说明。
    怎么求next数组呢?
    先展示一下code:
  //先求出next数组,具体思路/**数组下标是出现不同的字符的位置【next数组中需要每一个都考虑到,即是遍历所有】,值为回溯到的位置,相当于将前缀的公共重复子串副高后缀的重复公共子串,这里需要注意的是,前缀与后缀的重复子串均不同与需要计算的* 子串长度相同,否则没有意义* 可以定义两个指针,一个指针记录当前的下标,另一个记录上一次的最大公共子串的位置,这个如果字串的长度加一,则只需要将判断上一次最大子串位置的指针的下一个元素* 是否相等,要是相等,则直接加入当前位置的最大重复子串【因为前面的最大子串是验证过的,只需要确定当前的相同即可以确定】,若是不同,则回溯* 回溯:这里的回溯比较难理解,可以这样理解,对于新增加的字串字符,我先不考虑与上一次最大重复子串的下一个字符是否相同,而是直接右移,那么此时,我记录位置的指针对应的就是上一次最大子串的的下一个元素* 即回溯到该位置后,我进行比较,发现这两个元素并不相同,那我应该怎么办呢?答案肯定是继续右移,即当前这个位置对应的最大重复的字串的位置【next数组中对应的回溯位置】* 那么再求该位置的最大重复子串时候就会转化为移动后的位置的最大子串 即最大子串指针的位置 = next[当前最大子串指针的位置],若是与新增加的字符相等了+1后则是该位置对应的指针位置,否则则继续右移,直至相同,就是该* 位置需要回溯的位置。*/
private int[] next;public void findNext(String str){//初始化next数组next = new int[str.length()+1];//前缀最大重复子串指针的位置int k = 0;//位置指针int j = 1;//next[0]没有使用,默认为0next[j] = 0;//判断是否到达尾部while (j<str.length()){//当k==0的时候代表第二个字符if(k==0 || str.charAt(j)==str.charAt(k)) {//新增的一个字符的位置,由于k是上一最大可重复子串的位置,所以只需要判断新增加的位置即可。记住:计算的子串是该字符之前的,并不包含此字符,//而是当当前字符不同时,之前的最大公共重复子串++j;//可重复子串指针位置加一,即n+1++k;//记录当前位置的对应的可重复子串的位置指针next[j] = k;}else {//回溯,相当于直接右移,求右移后位置的可重复子串的位置k = next[k];}}}

下面我们通过一个例子来手动计算一个next数组,并与上面的代码对应一下
我们假设一个字符串为ababa

  1. 第一步,由于在字符串匹配的时候任意位置都有可能与源串匹配出不同,那么我们就要考虑到所有的情况,即遍历T,并求出每一位置的前部分子串的前后缀的最大公共重复的子串
  2. 假设遍历T的指针为j,前缀的指针为k,对于求最大公共重复的子串我们分为三种情况:①j=1时,next[1]= 0,②当含有重复公共子串的时候,next[j+1]=k+1【这也是上面为什么求前缀的最大重复子串+1的坐标,即K+1】,③当没有重复公共子串的时候,next[j+1] = 1。记住上面三种情况,那么我们开始进行遍历【记住,我们从1开始遍历的,并不是0,也就是第一个a的坐标为1
  3. j=1时,此时next[1] = 0
  4. 当j=2时,我们得到 a ,我们不考虑现在指针正在指向的字符【b】,它之前的只有一个a,没有最大重复子串,即next[2] = 1
  5. 当j=3时,我们得到ab,也没有,则next[3] = 1
  6. 当j=4时,我们得到aba,此时的前缀最大串是a,即a的位置+1 = 2,则next[4] = 2
  7. 当j=5时,我们得到abab,此时的前缀最大串是ab,即b的位置+1 = 3,则next[5] = 3
  8. 当j=6时,我们得到ababa,此时的前缀最大串是aba,则a的位置+1 = 4,则next[6] = 4,这样就完成了遍历,得到了数组next。
    那这个next数组是怎么使用的呢?
    我们先看代码
/**** @param str 需要匹配的子串* @param targetStr 被匹配的子串* @param position 开始的位置* @return 是否匹配成功*/public boolean kpmMethod(String str,String targetStr,int position){//定义一个指针记录需要被匹配的子串位置int positionPoint = position;//定义匹配子串的位置,由于next[0] = 0,相当于保留了,所以要从1开始int sonStrPoint = 1;//先计算出next数组findNext(targetStr);//如果均未到达尾部,则继续循环while (positionPoint<str.length() && sonStrPoint<targetStr.length()){// 要判断sonStrPoint不能为0,由于next长度是targetStr的长度+1,所以要减掉1if(sonStrPoint==0 || str.charAt(positionPoint)==targetStr.charAt(sonStrPoint-1)){++positionPoint;++sonStrPoint;}else {//代表出现不同,则回溯到next指定的位置中,相当于右移sonStrPoint = next[sonStrPoint];}}return positionPoint != str.length();}

下面我们看一下执行过程

  • 我们看到,当j=2的时候出现了不同,那么我们就需要右移,但是我们并不需要只右移一位,我们看到ab,根据next数组求值方法我们可以看到ab没有最大公共子串,则next[2+1] = 1,则j要指到a的位置,即右移两位,j此时应该指向坐标1,如2图
    在这里插入图片描述

  • 下面的步骤可以看出,最大的公共重复子串为a,则next数组应该是next[4] = 2,所以j此时应该指向坐标2,即b的位置,相当于右移三位,如图三
    在这里插入图片描述

  • 最后我们可以匹配到正确的子串位置

在这里插入图片描述

我们可以推算出KPM的时间复杂度为O(L(S)+L(T))
部分图片来自:https://blog.csdn.net/yyzsir/article/details/89462339


http://chatgpt.dhexx.cn/article/uVfudRki.shtml

相关文章

KPM算法

算法 字符串匹配之朴素算法和KMP算法及JAVA代码实现 2017年06月02日 10:31:12 阅读数&#xff1a;941 暴力匹配算法 假设现在我们面临这样一个问题&#xff1a;有一个文本串S&#xff0c;和一个模式串P&#xff0c;现在要查找P在S中的位置&#xff0c;怎么查找呢&#xff1…

Python KPM算法

知识点说明&#xff1a; 先说前缀&#xff0c;和后缀吧 比如有一个串&#xff1a;abab 则在下标为3处的&#xff08;前缀和后缀都要比下标出的长度小1&#xff0c;此处下标为3出的长度是4&#xff09; 前缀为&#xff1a;a,ab,aba 后缀为&#xff1a;b,ba,bab 一、要获取…

KPM算法——数据结构|复习局|串|复杂模式匹配算法|二维数组解决KPM

数据结构复习局——KPM算法 何为KPM&#xff1f;事先规则状态匹配dp——状态转移图状态X获得dp数组值看看图再理解下 写在前面&#xff1a; 本文仅为作者个人学习记录&#xff0c;详细具体内容参考自知乎大佬labuladong &#x1f448;点击与大佬&#x1f93a;击剑&#x1f93a;…

KMP算法原理及实例

KMP是为了解决串的匹配问题。 一、基础知识 1、概念 1.串的匹配问题&#xff1a;就是在一个长的主串s中找到另一个的短的子串t。 2.目标串&#xff08;主串\文本串&#xff09;&#xff1a;被匹配的母串&#xff0c;串s被称为目标串。 3.模式串(子串&#xff09;&#xff1a…

KPM算法思想及实现

一、比较暴力算法和KMP算法 1、暴力算法&#xff1a; 双指针遍历主串和子串&#xff0c;当发现主串和子串不匹配时&#xff0c;双指针同时回溯 2、KMP算法&#xff1a; 双指针遍历主串和子串&#xff0c;当发现主串和子串不匹配时&#xff0c;通过比较子串的next数组只回溯…

正定矩阵的性质

正定矩阵的定义&#xff1a;若矩阵A是n阶方阵&#xff0c;并且它的二次型大于0&#xff0c;即&#xff0c;则矩阵A是正定矩阵。 正定矩阵的性质&#xff1a; 正定矩阵的所有特征值都为正数。正定矩阵行列式为正数两个正定矩阵的和为正定矩阵&#xff08;两个正定矩阵的乘积不…

顺序主子式

设A为 阶矩阵&#xff0c;子式 称为A的i阶顺序主子式。 [1] 对于 阶的矩阵A&#xff0c;其共有n阶顺序主子式&#xff0c;即矩阵A的顺序主子式由 共n个行列式按顺序排列而成。

【矩阵论笔记】平方根分解

定义 例子 首先判断顺序主子式。 R矩阵每一行除以对角元 平方根分解推导 因为A的分解是唯一的&#xff0c;可以得到 L R T LR^{T} LRT 例题 待定系数法

MATLAB_数值计算_用平方根法解线性方程组—(Cholesky分解)

利用对称正定矩阵的乔累斯基分解求解对称正定方程组的方法称为平方根法对称正定矩阵A的对角元为正实对称矩阵A正定的充要条件是A的所有特征值为正对称正定矩阵非奇异&#xff0c;其逆亦为对称正定矩阵实对称矩阵A正定的充要条件是A的所有顺序主子式为正正定矩阵的顺序主子阵是正…

正定与半正定矩阵,判别的方法不能混用,否则出错

坑&#xff1a;特征值有0可以知道该矩阵不可能正定&#xff0c;那可以用顺序主子式判断是否为半正定吗&#xff1f; 答案&#xff1a;不能 例子&#xff1a;A,特征值为一个0&#xff0c;两个正数>那就是半正定啦呀 但是&#xff0c;主子式二阶小于0那就不正定了呀两种方法…

线性代数【11】二次型

前言&#xff1a; 矩阵表达的是线性关系的方程组&#xff0c;但是&#xff0c;客官世界&#xff0c;是包括稍微复杂的&#xff0c;二次方程。 尤其几何中&#xff0c;有二次曲线&#xff0c;二次型&#xff0c;就是一个多元函数&#xff0c;是多个变量的二次&#xff0c;齐次…

Lyapunov稳定性分析1(正定函数、二次型正定判定)

一、 正定函数 1.1 定义&#xff1a; 令V(x)是向量x的标量函数&#xff0c;S是x空间包含原点的封闭有限区域。如果对于S中的所有x&#xff0c;都有&#xff1a; 则V(x)是正定的&#xff08;半正定&#xff09;。正定函数更直观的描述如下图所示&#xff1a; 如果条件(3&a…

牛顿法为什么要保证Hessian矩阵正定

牛顿法为什么要保证Hessian矩阵正定&#xff1a; 实际中&#xff0c;需要求出Hessian的逆矩阵&#xff0c;只有正定矩阵&#xff0c;才可以求出逆矩阵。 正定矩阵&#xff1a;特征值全大于0&#xff1b;各阶主子式全大于0.

正定矩阵的相关知识

一、正定矩阵的定义&#xff1a;若矩阵A是n阶方阵&#xff0c;并且它的二次型大于0&#xff0c;即 则矩阵A是正定矩阵。 二、正定矩阵的性质&#xff1a; 1.正定矩阵的所有特征值都为正数。 2.正定矩阵行列式为正数 3.两个正定矩阵的和为正定矩阵&#xff08;两个正定矩阵的乘…

顺序主子式的英文翻译(定义)

顺序主子式的英文翻译&#xff08;定义&#xff09; 为了查明顺序主子式的英文翻译&#xff0c;我在国内知网翻译助手、金山词霸等诸多翻译系统查了一下&#xff0c;给出的答案不外乎以下几个答案。 &#xff08;知网翻译助手的答案&#xff09; 我喜欢刨根问底&#xff0c;很明…

030 正定二次型及判别法之定义法、特征值法、顺序主子式法

030 正定二次型及判别法之定义法、特征值法、顺序主子式法

matlab-线性代数 det 各阶主子式、余子式、代数余子式

2019独角兽企业重金招聘Python工程师标准>>> matlab : R2018a 64bit     OS : Windows 10 x64typesetting : Markdown    blog : my.oschina.net/zhichengjiu    gitee : gitee.com/zhichengjiu 各阶主子式 code clear clca=[1 2 3;4 5 6;6 7 8…

主子式、顺序主子式、余子式、代数余子式

K阶子式 [ 1 ] ^{[1]} [1] (Minor) 以3阶行列式为例&#xff1a; ∣ a 1 a 2 a 3 b 1 b 2 b 3 c 1 c 2 c 3 ∣ \left| \begin{array} {ccc} a_1 & a_2 & a_3 \\ b_1 & b_2 & b_3\\ c_1 & c_2 & c_3 \end{array} \right| ∣∣∣∣∣∣​a1​b1​c1​​…

简单推导:关于矩阵主子式的几点性质

1.名词介绍: 特征多项式&#xff1a;在数域P上的某个方阵A,则行列式即为其特征多项式&#xff0c;简记为; 逆序数&#xff1a;1,2,...n的某个排序相对自然序列相反的个数&#xff1b;记为&#xff1a; 主子式&#xff1a;某个行列式的部分列和部分行&#xff1a;行号和列号一…

Zlib库的安装与使用

在实际应用中经常会遇到要压缩数据的问题&#xff0c;常见的压缩格式有zip和rar,而Linux下那就更多了,bz2,gz,xz什么的都有&#xff0c;单单Linux下的解压和压缩命令就有好多呢&#xff1f;没有什么好不好的。查了资料&#xff0c;应该是zlib这个比较简单好用。应用也广&#x…