前言
解决问题是字符串单模匹配。
其他算法可以参考博文链接
文本串S：
dfgabcabcda
模式串T：abcabc
n为S的长度，即n = 11;
m为T的长度，即m = 6;
i为匹配时 S的下标；
j为匹配时T的下标。
对比：
在BF朴素算法的中每次匹配，如果匹配失败，i会从匹配开始前的i往后移动一位。j则会直接变为0；
而在KMP算法中，将会被优化为i不会后退，j每次为使得模式串T与文本串S匹配的头部更加往后的一个下标。
怎么实现呢？
先上代码：
代码
#include<iostream>
#include<string>
#include<vector>
#ifdef D
#define DBG(fmt,arg...) printf(fmt,##arg)
#else
#define DBG(fmt,arg...) {}
#endif
using namespace std;
vector<int> mynext;
void Getmynext(string s){
int n = s.size();
mynext = vector<int>(n,-1);
mynext[0] = -1;
mynext[1] = 0;
DBG("NEXT = [ -1 0 ");
for(int j = 2; j < n; ++j){
if(mynext[j - 1] != 0 && s[mynext[j - 1]] == s[j - 1]){
mynext[j] = mynext[j - 1]+1;
}else if(s[0] == s[j - 1]){
mynext[j] = 1;
}else{
mynext[j] = 0;
}
DBG("%d ",mynext[j]);
}
DBG("]\n");
return ;
}
int KMP(string &A,string &B){
int n = A.size();
int m = B.size();
if(n < m) return -1;
int i = 0, j = 0;
while(i < n && j < m){
if(A[i] == B[j]){
DBG("\033[32m while i = %d and j = %d, they are equaled !\033[0m\n",i,j);
++i;
++j;
}else{
DBG("\033[35;5m while i = %d and j = %d, they are noequaled !\033[0m\n",i,j);
j = mynext[j];
if(j == -1){
++i;
j = 0;
}
DBG("\033[33mthen changed i = %d and j = %d!\033[0m\n",i,j);
}
}
if(j >= m) return i - m;
return -1;
}
int main(){
string A,B;
cin >> A >> B;
Getmynext(B);
DBG("\033[32mi get the vector next!\033[0m\n");
int index = KMP(A,B);
cout << "i find the model string in the index "<<index <<" of the main string !!"<<endl;
return 0;
}
结果为：
分析
首先，需要理解next数组：
看代码。
不从原理往现象理解，我们从现象往原理理解。
构建问题环境：
文本串S：
dfgabcabcda
模式串T：abcabc
n为S的长度，即n = 11;
m为T的长度，即m = 6;
i为匹配时 S的下标；
j为匹配时T的下标。
next数组的产生与意义
-
next数组是根据模式串T产生的。
T=abcabc
next数组为[-1 0 0 0 1 2] -
next[j]代表什么呢？
代表如果S的i和T的j没匹配上，那么在KMP算法中此时i应该再去和T中的哪个j比较？.
可以看出，并没有打算让i从匹配起始位置往后移动一位，而是我都到这里了，我就不动了，，你模式串中的j找出一个来和我继续匹配。
比如
"abcdabce"和“abce"匹配，第一次匹配i= 3，指向d和j= 3指向e没匹配上，朴素匹配就会让i直接到i= 1,让j重新到0；
而KMP就会保持i = 3不变，找一个j来和我匹配。
next数组作用过程步步分析
- i = 0, j = 0;没匹配上，
此时代码段中的j = next[j];if(j == -1){i = i + 1; j = 0};生效，将i 变为1，就右变成next[0] = -1,然后j = 0;- 看结果展示中绿色的调试信息，发现i = 3时开始匹配上。
next数组到底是什么？
可以看next数组的意义 ，next[j]就是此时i与j匹配失败时i不变的话，j 应该是多少？
此时满足的条件:
如果j== -1，说明i要和T的下标为-1出开始匹配。
如果j >= 0，说明i要和T下摆哦为next[j]出重新匹配。此时就满足的是，S中i往前next[j]- 1个字母与T中前next[j] - 1个字母相同。
你把这个满足条件理解了，你就会发现从另一个方向理解了next数组。
就比如说下边这个很经典的结果，你看一下i和j的变化就明白了。
