类似于BM里的概念:坏字符(不能匹配的),好前缀(已经匹配的那段)
借一张图理解一下:
上面可以看出,可以事先预处理好模式串,与主串比较时,直接用next数组
方法2: case1
case2
如果 b[k] != b[j] , 则我要在前面部分里寻找能和包含 b[j] 的后缀匹配的最长前缀子串; b[k] 前面的最长匹配前缀长度就是 next[k],那么其后面一个字符就是 b[ next[k] ],如果它等于b[j],那么next[j+1] = next[k] + 1 参考文献
王争的代码不好理解,找了书和别的人的代码参考
/**
* @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)