经典算法之KMP算法
程序员文章站
2022-05-02 17:39:46
...
简介
KMP算法是一种改进的字符串匹配算法,由D.E.Knuth,J.H.Morris和V.R.Pratt同时发现,因此人们称它为克努特——莫里斯——普拉特操作(简称KMP算法)。KMP算法的关键是利用匹配失败后的信息,尽量减少模式串与主串的匹配次数以达到快速匹配的目的。具体实现就是实现一个next()函数,函数本身包含了模式串的局部匹配信息。时间复杂度O(m+n)。
-
题目展示
- 给出两个字符串s1(主串)和s2(模式串),判断s2是否是s1的子串.
- 输入两行
- 第一行:主串s1
- 第二行:模式串s2
- 输出第一个匹配的位置(下标),若s1不包含s2子串,输出-1。
- 例
- 主串s1:ababcababeaf
- 模式串s2:ababe 模式串s2:ababecf
- 输出:5 输出:-1
吐槽一下:KMP算法代码实现简单,但理解起来比较困难,博主学习第一遍的时候以为领略到了精华,然一切皆是假象,又反过头重新来过,牛掰的算法值得记录一下。
笨方法解读
-
从主串s1中匹配模式串s2,我们从左至右依次以s1的每个字符为起点匹配。
- 情况一:在主串s1中可以找到与模式串s2相匹配的子串,遇到s2的结尾停止循环。
- 情况二:设当前位置为,主串s1当前位置到结尾的长度等于模式串的长度(),且主串s1当前位置字符不等于模式串s2首位置字符(),直接返回。原因:此后s1的子串长度小于s2的长度,肯定不能匹配。
代码段
#include<iostream>
#include<string>
using namespace std;
int getIndexOf(const string& s1, const string& s2) {
int len1 = s1.length(); //主串长度
int len2 = s2.length(); //模式串长度
int i1 = 0,i2 = 0; //下标遍历
while (i2 != len2) {
if (s1[i1] == s2[i2]) {
++i1;
++i2;
}
else {
if (len1 == len2)
return -1;
else {
i1 = i1 - i2 + 1;
i2 = 0;
--len1;
}
}
}
return i1 - i2;
}
int main(int argc, char* argv[]) {
string s1; //主串
cin >> s1;
string s2; //模式串
cin >> s2;
int index = getIndexOf(s1, s2);
index == -1 ? cout << "no" << endl : cout << "yes" << endl;
getchar();
return 0;
}
KMP算法
采用笨方法解读时,我们会发现主串s1中的某些下标根本无需与模式串s2匹配,图解示意如下。第(3)、(4)步的匹配是可以省略的,可直接跳到主串s1下标为2的位置往下匹配,这时KMP就登场了。
-
字符的最长前缀和最长后缀
- 最长前缀不包括最后一个字符
- 最长后缀不包括第一个字符
- 从前往后加字符形成前缀,从后往前加字符形成后缀。对于字符串s=”abcabe”的字符‘e’,最长前缀为”abca”,最长后缀为”bcab”。
- 前缀为a,后缀为b时,”a”!=”b”
- 前缀为ab,后缀为ab时,”ab”==”ab”
- 前缀为abc,后缀为cab时,”abc”!=”cab”
- 前缀为abca,后缀为bcab时,”abca”!=”bcab”
-
next数组
- next数组是KMP算法的精髓所在,数组长度与模式串s2的长度相等,下标中存储的值为模式串s2相对应字符的(前缀==后缀)时的长度。
- 第一个字符无前缀和后缀,因而默认为。
- 第二个字符前面只有一个字符,不满足最长前缀不包括最后一个字符,最长后缀不包括第一个字符的条件,因而默认为。
- next数组其他下标存储的值我们采用图形来理解。
- 情况一: s[i]==s[j],当前下标存储的值为上一个下标存储的值加1。为什么呢?因为如果可以加2加3,说明之前求取的(前缀==后缀)的最长长度是错误的。
- 情况二:s[i]!=s[j]。
- 第(3)步相等:next[j+1]=next[i]+1。
- 第(3)步不相等:循next[i]的下标继续比较,直到存储的值为-1为止,即长度为0。
- 情况一: s[i]==s[j],当前下标存储的值为上一个下标存储的值加1。为什么呢?因为如果可以加2加3,说明之前求取的(前缀==后缀)的最长长度是错误的。
代码段
void getNextArray(string s2, vector<int>& next) {
int len = s2.length();
if (len == 1) {
next[0] = -1;
return;
}
next[0] = -1;
next[1] = 0;
int cn = 0; //前缀的标志
int i = 2;
while (i < len) {
if (s2[i - 1] == s2[cn]) {
next[i++] = ++cn;
}
else if (cn > 0) {
cn = next[cn];
}
else {
next[i++] = 0;
}
}
return;
}
- KMP算法演示
#include<iostream>
#include<string>
#include<vector>
using namespace std;
void getNextArray(string s2, vector<int>& next) {
int len = s2.length();
if (len == 1) {
next[0] = -1;
return;
}
next[0] = -1;
next[1] = 0;
int cn = 0; //前缀的标志
int i = 2;
while (i < len) {
if (s2[i - 1] == s2[cn]) {
next[i++] = ++cn;
}
else if (cn > 0) {
cn = next[cn];
}
else {
next[i++] = 0;
}
}
return;
}
int getIndexOf(const string& s1, const string& s2) {
int len1 = s1.length();
int len2 = s2.length();
if (len1 < 0 || len2 < 0 || len1 < len2) {
return -1;
}
int i1 = 0, i2 = 0;
vector<int> next(len2);
getNextArray(s2, next);
while (i1!=len1 && i2!=len2) {
if (s1[i1] == s2[i2]) {
++i1;
++i2;
}
else if (next[i2] == -1) {
++i1;
}
else {
i2 = next[i2];
}
}
return i2 == len2 ? i1 - i2 : -1;
}
int main(int argc, char* argv[]) {
string s1; //主串
cin >> s1;
string s2; //模式串
cin >> s2;
int index = getIndexOf(s1, s2);
index == -1 ? cout << "no" << endl : cout << "yes" << endl;
getchar();
return 0;
}
上一篇: 手把手带你开发豆瓣FM(vue)
下一篇: KMP学习困惑点,自学自闭自问自答