字符串匹配算法（KMP）
1. KMP由来
- 上一节说的BM算法是最高效、最常用的字符串匹配算法。
- 最知名的却是KMP，它3位作者（D.E.Knuth，J.H.Morris，V.R.Pratt），算法的全称是Knuth Morris Pratt 算法，简称KMP算法。
2. KMP算法基本原理
类似于BM里的概念：坏字符（不能匹配的），好前缀（已经匹配的那段）
在这里插入图片描述
在这里插入图片描述
- KMP算法目的：当遇到坏字符后，对于已经对比过的好前缀，将模式串多滑动几位
在这里插入图片描述
借一张图理解一下：
在这里插入图片描述
在这里插入图片描述
上面可以看出，可以事先预处理好模式串，与主串比较时，直接用next数组
- 构建next数组（失效函数） next 数组含义：当前字符之前的字符串（不含当前）中，最大长度的相同前缀后缀子串。如果next [j] = k，代表 j 之前的字符串中有最大长度为 k 的相同前缀后缀子串。
- 失效函数计算方法 方法1：暴力求解子串长度，效率低
在这里插入图片描述
方法2： case1
在这里插入图片描述
case2
在这里插入图片描述
如果 b[k] != b[j] , 则我要在前面部分里寻找能和包含 b[j] 的后缀匹配的最长前缀子串； b[k] 前面的最长匹配前缀长度就是 next[k]，那么其后面一个字符就是 b[ next[k] ]，如果它等于b[j]，那么next[j+1] = next[k] + 1 参考文献
3. 代码
王争的代码不好理解，找了书和别的人的代码参考
/**
* @description: KMP字符串匹配算法
* @author: michael ming
* @date: 2019/6/22 17:15
* @modified by:
*/
#include <string>
#include <iostream>
using namespace std;
void calNexts(char *b, int m, int *next)
{
next[0] = -1;
int j = 0, k = -1;
while(j < m)
{
if(k == -1 || b[j] == b[k])
{
j++;k++;
next[j] = k;
}
else
k = next[k];
}
// for(j = 0; j < m; ++j)//调试代码
// cout << "next[" << j << "] " << next[j] << endl;
}
int str_kmp(char *a, int n, char *b, int m)
{
int *next = new int [m];
calNexts(b, m, next);
int i = 0, j = 0;
while(i < n && j < m)
{
if(j == -1 || a[i] == b[j])
{
i++;j++;
}
else
{
j = next[j];
}
}
if(j == m)
{
delete [] next;
return i-j;
}
delete [] next;
return -1;
}
int main()
{
string a = "abcacabcbcbaccba", b = "cbaccba";
cout << a << "中第一次出现" << b << "的位置(从0开始)是：" << str_kmp(&a[0],a.size(),&b[0],b.size());
return 0;
}时间复杂度O（n+m），空间复杂度O（m）
本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2019/06/22 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录
腾讯云开发者
