【C++】算法集锦(10)通俗讲kmp算法
什么是KMP算法
它是一个字符串匹配算法。
KMP算法的优势
(就恨当初写kmp那篇的时候,没有留下图解,全篇文字铺开,现在我自己都看不懂了)
首先,给定 “主串” 和 “模式串” 如下:
BF算法使用简单粗暴的方式,对主串和模式串进行逐个字符的比较:
第二轮,模式串向后挪动一位,和主串的第二个等长子串比较,发现第0位字符不一致:
第三轮,模式串继续向后挪动一位,和主串的第三个等长子串比较,发现第0位字符不一致:
···
···
这种算法的缺点很明显,做了很多无谓的比较,还好,我们今天讲的不是这种算法。
KMP算法
第一轮,模式串和主串的第一个等长子串比较,发现前5个字符都是匹配的,第6个字符不匹配,是一个“坏字符”:
这时候,如何有效利用已匹配的前缀 “GTGTG” 呢?
我们可以发现,在前缀“GTGTG”当中,后三个字符“GTG”和前三位字符“GTG”是相同的:
在下一轮的比较时,只有把这两个相同的片段对齐,才有可能出现匹配。这两个字符串片段,分别叫做最长可匹配后缀子串和最长可匹配前缀子串。
第二轮,我们直接把模式串向后移动两位,让两个“GTG”对齐,继续从刚才主串的坏字符A开始进行比较:
显然,主串的字符A仍然是坏字符,这时候的匹配前缀缩短成了GTG:
按照第一轮的思路,我们来重新确定最长可匹配后缀子串和最长可匹配前缀子串:
第三轮,我们再次把模式串向后移动两位,让两个“G”对齐,继续从刚才主串的坏字符A开始进行比较:
···
···
next数组
什么是next数组?next数组用来干什么?
next数组是决定kmp算法快速移动的核心。
好,我们来看一下next数组是如何生成的。
有了next数组,我们就可以通过已匹配前缀的下一个位置(坏字符位置),快速寻找到最长可匹配前缀的下一个位置,然后把这两个位置对齐。
比如下面的场景,我们通过坏字符下标5,可以找到next[5]=3,即最长可匹配前缀的下一个位置:
生成next数组
我先放一段代码再这里:
(如果用上面那张图里的方法,那生成next数组的过程是非常低效的)
void getnext(string p, vector<int> &next) //next在传入时应该进行扩容
{
int len = p.size();
int k = -1;
int j = 0;
next[0]=-1;
while (j < len - 1)
{
if (k == -1 || p[k] == p[j])
{
k++;
j++;
next[j] = k;
}
else {
k = next[k];
}
}
}
能看懂吗?
首先为了后面运算方便,将next[0]设置为-1,不得不说这个设置为-1非常之巧妙。
先不说巧妙在哪里,自己去写的话就知道了。
也先不说那个令人绞尽脑汁的 k = next[k]
,我们先把基础弄明白。
先看next[j] = k
,这一句。
来我们来个简单的栗子:“ababcba”.
要对这个子串求它的next数组,是这样的。
1、a
2、ab
3、aba
4、abab
5、ababc
6、ababcb
7、ababcba
将这个字符串这样分一下,然后对号入座,看到我标的号了没,对应的是next数组中的号,最后那个可以去掉,因为如果整个串都对上了还回溯什么。
首先我们来看一下“前后子集“的概念,我自己起的名字,还不错吧。
拿4来说把,它的前子集有:
{
a,
ab,
aba
}
后子集有:
{
b,
ab,
bab
}
规律不难找啊。
那,他俩子集里面有一个同类,“ab”,将ab的长度填入next[4]里面。
接下来难度要稍微升级了。
这个next数组,也有半自动推导,碧如说4(abab),它的对称度为2,那么如果在4的基础上,加上一个字符,这个字符刚好跟对称度+1的位置的字符对上,即如果加上的字符是a,那么便可以知道 5 的对称度为3,因为前面两个已经有 4 做了铺垫。
这就是:
if (k == -1 || p[k] == p[j])
{
k++;
j++;
next[j] = k;
}
这一个部分的原理。next[++j] = ++k;
,是这样来的。
可惜,上面那个例子加上去的是 ‘c’。那就·是另外一部分代码的事情了:
else {
k = next[k];
}
k = next[k]
要理解这行代码,我们用另外一个字符串会比较直观一些。
“a b a b a b c b”
一步一步来啊,
1、a
next[0] = -1;
k = -1,j=0;
k = 0,j=1;
next[1] = 0; //进入了if
//这两个简直是铁索连环,就写一起吧
2、a,b
j = 1,k = 0; //进入else
k = -1; //所以,嗯
//再一圈循环
k = 0,j = 2; //进入if
next[2] = 0;
3、a,b,a
//进入if
k = 1,j = 3;
next[3] = 1;
4、a,b,a,b
k = 2,j = 4;
next[4] = 2;
//看啊,用到上面讲的了。
//其实还有一条铁律忘记说了,如果有耐心看到这里那我就说。后一位的对称度,顶多比前一位,多1!!!
5、a,b,a,b,a
k = 3,j = 5;
next[5] = 3;
6、a,b,a,b,a,b
k = 4,j = 6;
next[6] = 4;
//越来越接近目标了啊,马上就要断了香火了
7、a,b,a,b,*a*,b,c
// ‘c’!=‘a’!
// 进入else
k = next[4] = 2
// 循环,进入else
k = next[2] = 0
// 再循环,
k = -1
// 再循环,进入if
k = 0,j = 7
next[7] = 0
-----
这时候你会发现,它新加上来的那个字符,和对称度后面一位字符不匹配,‘c’!=‘a’!,那里我打了星标。
KMP匹配、
这个匹配就比较好理解了,该注释的地方我注释了
int kmp(string s, string p)
{
int i = 0;
int j = 0;
int sLen = s.size();
int pLen = p.size();
if (pLen == 0 )
return 0;
vector<int> vec(pLen, 0);
getnext(p,vec); //获取next数组
while (i < sLen && j < pLen)
{
if (j == -1 || s[i] == p[j])
{
i++;
j++;
}
else
{
//②如果j != -1,且当前字符匹配失败(即S[i] != P[j]),则令 i 不变,j = next[j]
//next[j]即为j所对应的next值
j = vec[j];
}
}
if (j >= pLen)
return(i - j);
return -1;
}
KMP算法整体实现(LeetCode测试通过)
#include<iostream>
#include<string>
#include<vector>
using namespace std;
void getnext(string p, vector<int> &next) //next在传入时应该进行扩容
{
int len = p.size();
int k = -1;
int j = 0;
next[0]=-1;
while (j < len - 1)
{
if (k == -1 || p[k] == p[j])
{
k++;
j++;
next[j] = k;
}
else {
k = next[k];
}
}
}
int kmp(string s, string p)
{
int i = 0;
int j = 0;
int sLen = s.size();
int pLen = p.size();
if (pLen == 0 )
return 0;
vector<int> vec(pLen, 0);
getnext(p,vec); //获取next数组
while (i < sLen && j < pLen)
{
if (j == -1 || s[i] == p[j])
{
i++;
j++;
}
else
{
//②如果j != -1,且当前字符匹配失败(即S[i] != P[j]),则令 i 不变,j = next[j]
//next[j]即为j所对应的next值
j = vec[j];
}
}
if (j >= pLen)
return(i - j);
return -1;
}
int main()
{
vector<int> vec1(10,0);
//for (int i = 0; i < vec1.size(); i++)
// cout << vec1[i] << " ";
//cout << endl;
string str = "";
string str2 = "";
int a = kmp(str,str2);
cout << a << endl;
/*getnext(str2,vec1);
for(int i = 0;i<vec1.size();i++)
cout << vec1[i]<<" ";
cout << endl;*/
}
注:图来自《小灰的漫画算法之旅》
相关文章
- C++类构造函数初始化列表
- 【C/C++学院】0829-位容器multimapmutisetString/算法函数兰不达表达式以及类重载/GPU编程
- Win10系列:VC++调用自定义组件3
- Windows下pip安装包报错:Microsoft Visual C++ 9.0 is required Unable to find vcvarsall.bat
- (C++)关于i++和i++的左值、右值问题
- C++11时代的标准库快餐教程(4) - 排序算法的应用
- C++ code:数值计算之辛普生(Simpson)法求解积分问题
- Open3D(C++) ICP算法实现点云精配准
- 【C++竞赛 G】Lines
- Algorithm:C++语言实现之字符串相关算法(字符串的循环左移、字符串的全排列、带有同个字符的全排列、串匹配问题的BF算法和KMP算法)
- Qt-跨平台的C++图形用户界面应用程序框架(一)
- 解答私信@被c++折磨头秃的花季美少女 //C++ 利用指针数组输入10个单词,编写函数对10个单词进行排序并输出,要求判断是否有相同的单词,如果有相同的单词在输出时该单词只输出一次。
- 解答私信@被c++折磨头秃的花季美少女 //C++ 编写一个进阶版的进制转换程序,运行功能如下:请选择要输入的数字的进制(2、8、10、16):请输入该数字:请选择要转换成的进制(2、8。。。
- C++之enum class简单使用
- C++有序vector之每插入一个元素后重新排序
- C++:const_cast
- C++ Primer 学习笔记_41_STL实践与分析(15)--先来看看算法【下一个】
- 【强力推荐】基于Nvidia-Docker-Linux(Ubuntu18.04)平台:新版OpenCV5.x(C++)联合CUDA11.1(GPU)完美配置视觉算法开发环境
- C++之指针的引用与指针的指针讲解(一百一三十四)
- Windows和Linux下排查C++软件异常的常用调试器与内存检测工具详细介绍
- 代理模式C++实现
- PAT 1142 C++版
- 【PAT 1143】 Lowest Common Ancestor 【C++版】
- C++算法之神奇的位运算
- C++算法之动态规划一
- 黑马C++笔记——职工管理系统(C++实现)
- Stable Matching-稳定匹配问题【G-S算法,c++】
- 【跟学C++】C++STL三大主要组件——容器/迭代器/算法(Study19)
- 【C++】算法集锦(9):背包问题
- 一文带你弄懂C++中的ANSI、Unicode和UTF8三种字符编码及相互转换