关键词:
眼睛为她下着雨,心却为她打着伞、
在上篇中,我们讲到了BF暴力模式匹配算法。下面我们将讲述BF算法的优化版本算法KMP算法。
🎃KMP
定义
我们知道BF算法效率低的原因就是要回溯,即在匹配失败后,子串回溯到0,主串回溯到本趟匹配开始的下一个位置。而在KMP算法中,当我们匹配失败了,主串是不进行回溯,一直回溯我们的匹配模式子串。
- 假设现在主串S匹配到 i 位置,模式串P匹配到 j 位置
- 如果j = -1,或者当前字符匹配成功(即S[i] == P[j]),都令i++,j++,继续匹配下一个字符;
- 如果j != -1,且当前字符匹配失败(即S[i] != P[j]),则令 i 不变,j = next[j]。此举意味着失配时,模式串P相对于文本串S向右移动了j - next [j] 位,移动到j移动到next[j]。之后我们可以写出如下代码:
int KMP(string str, string sub, size_t position)
int strlen = (int)str.size();
int sublen = (int)sub.size();
if (strlen == 0 || sublen == 0)
return -1;
if (position < 0 || position >= str.size())
return -1;
int i = (int)position;
int j = 0;
while (i < strlen && j < sublen)
if (j == -1 || str[i] == sub[j])
++i; //如果匹配,一起++
++j;
else //如果不匹配,则回溯倒next[j]的位置
j = next[j];
//i-j得位置就是我们开始匹配的第一个字符的位置,j就等于我们的sublen
if (j >= sublen)
return i - j;
//没有匹配返回-1
else
return -1;
在上面中我们会发现有一个next数组,而next数组中的每一个值的含义:代表当前字符之前的字符串中,有多大长度的相同前缀后缀。
KMP的精髓就是next数组,也就是用next[j]=k;来表示,不同的j来对应一个k值,这个k就是你将来要移动到的j要移到(回溯)的位置。
而K的值是怎么求的呢?
- 规则:找到匹配成功的部分的两个相等的真子串(不包括自身),一个以下标0开始,另一个以j-1下标结尾。
- 不管什么数据的next数组的前两个数据都为next[0]=-1;next[1]=0;在这里,我们以下标来开始,而说到的第几个第几个是从1开始。
我们以abcabc为例,由于next[0]=-1;next[1]=0;是默认的,所以我们从j=2开始。
我们发现T[0]=‘a’, T[j-1]=‘c’,此时我们并没有找到两个相同的真子串,所以j所在的位置的k值为0,匹配失败后依旧回溯到0下标。
到了这里我们可以看到有两个匹配的真子串为a。
j走到末尾后,我们可以找到以a开始以b结尾的两个真子串为ab
既然我们知道了怎么手动求next数组,那下面我举几个例子大家来算一下。
示例:a b a b c a b c d a b c d e,求其next数组?
推导
我们假设next[i]=k是成立的
,所以当我们next[i]==1时,我们就知道了k在那个位置,进而才有下面的推导过程。
那我们是不是可以得到T[0] ~ T[k-1] == [x] ~ T[i-1] , 但这个x是不确定的,但我们可以去推导得到它。从上面得到式子那我们进而可以得到:
- k-1-0 == i-1-x,x= i-k。
- T[0] ~ T[k-1] == [i-k] ~ T[i-1]
当T[i] == T[k] && T[0] ~ T[k-1] == [i-k] ~ T[i-1] 时,推导出next[i+1]的值。next[i+1]=k+1.
当T[i] !=T[k]时,不相等时,我们此时k就要回溯,回溯到相等的下标或者等于-1时停止。所以此时的next[i+1]=k+1。
本质就是一直回溯要找T[i] == T[k]。然后next[i+1]=k+1。
如果k=-1,就说明是走到了第一个元素还不匹配就是说明没有两个不相同的真子串的情况也让它进入上面的相等T[i] == T[k]的条件里。此时k==-1,那么next[i+1]=k+1,此时就让他从0开始匹配。
🎃代码实现
void GetNext(vector<int>& next,const string&sub) //得到next数组
next[0]=-1;
next[1]=0;
int k=0;
int i=1;
int sublen=sub.size();
//为什么是小于sublen-1呢?这是因为当i+1>=sublen时访问数组时会越界
while(i<sublen-1)
//这里next数组k回溯到等于-1时,此时就说明没有找到T[i] == T[k],此时也让它进来,
//表明该位置匹配失败后让它从头开始进行匹配
if(k==-1||sub[i]==sub[k])
next[i+1]=k+1; //如果sub[i]=sub[k],那么我们的next[i+1]=k+1
++i;
++k;
//下面这个if判断不要也行,只是在某些情况下可以优化next数组,让其只回溯一次
if(sub[next[i]]==sub[i]) //优化next数组
next[i]=next[next[i]];
else //如果sub[i]!=sub[k],那么k我们就一直回溯
k=next[k];
int KMP(string str,string sub,size_t position)
//这里的strlen是个变量不要和库函数里的strlen弄混淆。
//这里我取的名字不太好,大家看的时候注意点
int strlen=static_cast<int>(str.size());
int sublen=static_cast<int>(sub.size());
if(strlen==0||sublen==0)
return -1;
if(position<0||position>=str.size())
return -1;
int i=static_cast<int>position;
int j=0;
vector<int>next(sublen);
//得到next数组,并将next数组优化
GetNext(next,sub);
while(i<strlen&&j<sublen)
//为什么当j==-1时,也要进来呢,这是因为next[0]==-1,j会一直回退。
//j==-1了相当于第一个就匹配失败了,此时我们的主串S就得往下一个开始匹配
//j由于是等于 -1的,它也++就变为 0了,重头开始匹配
if(j==-1||str[i]==sub[j])
++i; //如果匹配,一起++
++j;
else //如果不匹配,则回溯倒next[j]的位置
j=next[j];
//i-j得位置就是我们开始匹配的第一个字符的位置,j就等于我们的sublen
if(j>=sublen)
return i-j;
//没有匹配返回-1
else
return -1;
如果小伙伴还没看懂可以在评论区留言,我会在评论区给你解答!
如有错误之处还请各位指出!!!
那本篇文章就到这里啦,下次再见啦!
模式匹配----kmp算法(代码片段)
...,心却为她打着伞、在上篇中,我们讲到了BF暴力模式匹配算法。下面我们将讲述BF算法的优化版本算法KMP算法。🎃KMP定义我们知道BF算法效率低的原因就是要回溯,即在匹配失败后,子串回溯到0,主串回... 查看详情
kmp算法(代码片段)
...法)。KMP算法的核心是利用匹配失败后的信息,尽量减少模式串与主串的匹配次数以达到快速匹配的目的。具体实现就是通过一个next()函数实现,函数本身包含了模式串的局部匹配信息。KMP算法的时间复杂度O(m+n)。原理匹配模式... 查看详情
串的模式匹配算法之kmp(代码片段)
title:串的模式匹配算法之kmptags:数据结构与算法之美author:辰砂1.引言首先我们需要了解串的模式算法目的:确定主串中所含子串第一次出现的位置(定位);常见的算法种类:BF算法(又称古典的、经典的、朴素的、穷举的),KM... 查看详情
单模式串匹配----浅谈kmp算法(代码片段)
模式串匹配,顾名思义,就是看一个串是否在另一个串中出现,出现了几次,在哪个位置出现; p.s. 模式串是前者,并且,我们称后一个(也就是被匹配的串)为文本串; 在这篇博客的代码里,s1均为文本串,s2均为模... 查看详情
kmp算法详解及其java实现(代码片段)
...法,又称作“看猫片”算法(误),是一种改进的字符串模式匹配算法,可以在O(n+m)的时间复杂度以内完成字符串的匹配操作,其核心思想在于:当一趟匹配过程中出现字符不匹配时,不需要回溯主串的指针,而是利用已经得到... 查看详情
串串的模式匹配算法(子串查找)bf算法kmp算法(代码片段)
串的定长顺序存储#defineMAXSTRLEN255,//超出这个长度则超出部分被舍去,称为截断串的模式匹配:串的定义:0个或多个字符组成的有限序列S=‘a1a2a3…….an‘n=0时为空串串的顺序存储结构:字符数组,串的长度就是数组末尾‘ 查看详情
字符串模式匹配中的bf算法与kmp算法(代码片段)
博客园的编辑器太难用了。。。。。。。。。。。BF算法即暴力算法,很简单,随便举个栗子:#include<iostream>#include<cstring>usingnamespacestd;//S[]:要匹配的链//T[]:模式串intBFsearch(intstart,charS[],charT[])intslen=strlen(S);inttlen=strlen(T 查看详情
改进kmp模式匹配算法(代码片段)
看了算法的大致步骤,然后自己一一证明了每一步的正确性,注释里写了一些理解。这也不是新鲜的做法,只是感觉这个程序非常精巧,反复地使用数学归纳法。让我感觉很新鲜。1/*2next[i]存放:match[i]处失配,orig在对应位置将要... 查看详情
kmp算法(代码片段)
...设现在我们面临这样一个问题:有一个文本串S,和一个模式串P,现在要查找P在S中的位置,怎么查找呢? 如果用暴力匹配的思路,并假设现在文本串S匹配到i位置,模式串P匹配到j位置,则有:如果当前字符匹配成功(... 查看详情
kmp算法(代码片段)
数据结构_串对于串,今天就总结了一个算法,关于字符串的模式匹配问题(重点在于kmp算法).普通的模式匹配算法,当匹配不成功时需要将主串的下标恢复到之前匹配的下一个字符,子串下标置为串首;而kmp算法则不需要重置主串的下标... 查看详情
数据结构串---kmp模式匹配算法实现及优化(代码片段)
KMP算法实现#define_CRT_SECURE_NO_WARNINGS#include<stdio.h>#include<stdlib.h>#include<string.h>#defineOK1#defineERROR0#defineTRUE1#defineFALSE0#defineMAXSIZE40typedefintElemType;typedefin 查看详情
4.2串的模式匹配算法(代码片段)
<?phpheader("content-type:text/html;charset=utf-8");classLinear_string/***串模式匹配算法**包括*1.串的初始化__contruct()*2.朴素的模式匹配算法index()*3.KMP模式匹配算法*4.改进的KMP模式匹配算法*/private$string;private$length;//构造函数p 查看详情
kmp算法字符串匹配算法(代码片段)
简介字符串的模式匹配是对字符串的基本操作之一,广泛应用于生物信息学、信息检索、拼写检查、语言翻译、数据压缩、网络入侵检测等领域,如何简化其复杂性一直是算法研究中的经典问题。字符串的模式匹配实质上就是寻... 查看详情
数据结构(c语言版)严蔚敏(字符串的模式匹配算法--kmp算法)(代码片段)
数据结构(C语言版)严蔚敏(字符串的模式匹配算法–KMP算法)1.暴力匹配算法//暴力匹配算法intIndex2(SStringS,SStringT)//S是主串,T是子串inti=0,j=0;while(i<S.length&&j<T.length)if(S.ch[i]==T.ch[j])i++;j+ 查看详情
数据结构(c语言版)严蔚敏(字符串的模式匹配算法--kmp算法)(代码片段)
数据结构(C语言版)严蔚敏(字符串的模式匹配算法–KMP算法)1.暴力匹配算法//暴力匹配算法intIndex2(SStringS,SStringT)//S是主串,T是子串inti=0,j=0;while(i<S.length&&j<T.length)if(S.ch[i]==T.ch[j])i++;j+ 查看详情
数据结构串---kmp模式匹配算法之获取next数组(代码片段)
(一)获取模式串T的next数组值1.回顾我们所知道的KMP算法next数组的作用next[j]表示当前模式串T的j下标对目标串S的i值失配时,我们应该使用模式串的下标为next[j]接着去和目标串失配的i值进行匹配而KMP算法的next求值函数我们可... 查看详情
❤️详解kmp算法(代码片段)
...f0c;KMP算法的核心是利用匹配失败后的信息,尽量减少模式串与主串的匹配次数以达到快速匹配的目的。具体实现就是通过一个next数组实现,next数组本身包含了模式串的局 查看详情
bf与kmp算法的初步认知(代码片段)
算法介绍BF(暴力匹配算法)代码实现KMP(模式匹配算法)举例分析(逻辑分析)next数组代码实现next组KMP算法的实现时间复杂度分析总结算法介绍BF(暴力匹配算法)BF算法,即暴力(BruteForce)算... 查看详情