KMP算法的探索
KMP是字符串比对中一种高效的算法，在数据结构课堂上时间短很难完全理解。
于是课后我又自己摸索了一番，根据自己的理解独立编写了程序
规定
为了下文叙述方便先规定几个统一的说法：
- 文本串：被比对的字符串；
- 模式串：比对的模板字符串；
- 指针i：指向文本串正在比对位置的指针；
- 一系列指针：下文结合程序注释；
- next数组、两种字符串下标均从1开始；
BF-算法
字符串比对中的暴力算法，没啥好说的，文本串逐位与模式串进行比较，不匹配则指针i回溯。例如：从i=1开始匹配，匹配到i=5时失败，回溯至i=2重新匹配。
next数组
关于KMP算法中最核心的思想蕴含在next[]数组中，next数组下标对应着字符串下标（下标从1开始，0位空置，至少我是空置）。顾名思义，next数组的值意义为本次“失配”后，下次匹配开始的位置（模式串的下标）。
思想动画
图A:源自于B站视频
图B:源自于B站视频
从图A到图B：第六位A失配后，很明显模式串发生了向右的滑动。
滑动的依据：滑动前箭头左侧的模式串前缀“AB”与后缀“AB”完全一致，由于箭头左侧已经匹配成功，所以对应的文本串也是一样的。这时候向右滑动既保证与文本串匹配，又避免了（滑动后）箭头左侧重复匹配操作。
滑动位数：即next数组的值。图中若以next数组表示，即位next[3] = 3。
- 两个‘3’均指模式串的第三位。翻译过来就是：当模式串中的第三位失配时，下一步从模式串的第三位继续匹配。
- 进一步抽象：有数组 next[x] = y，意思是：当模式串中的第x位失配时，下一步从模式串的第y位继续匹配。
上述 next[x] = y ，x没什么好说的就是模式串下标，下一步匹配位置y是如何得到的呢？
根据上图可以稍微总结一下：失配位置（箭头）左侧模式串前后缀一致的长度L加1，就是y。这个也很好理解，相当于我长度为L的子串已经匹配好了，那么只需要从L+1处继续匹配就好啦。
图片源于B站
这张图意在说明，在我们找一致的前后缀（很多人称为公共前后缀）的时候，是可能发生重叠的。
如果以上内容你看懂了
你就理解了next数组的求法了：即找出失配位置前，模式串子串的公共前后缀的最大长度L，并从L+1位开始继续匹配。
void cal_nextValue()
{
string t = compstr;
int m = 0; //记录能够匹配的公共前后缀的最大长度
if (t.size() <= 0) return;
next[1] = 0; //模式串第一位直接置0，该位置左侧子串长度为0
if (t.size() <= 1) return;
next[2] = 1;//第二位失配了，左侧最大公共前后缀只能为1
//从第三位开始，在失配位置左侧字符串寻找最长子串为公共前后缀
for (int i = 3; i < t.size(); i++)
{
// j为“左挡板”往右移动限定后缀,k为“右挡板”往左移动限定前缀
for (int k = i - 2, j = 2; j < i; j++, k--)
{
int flag = 1;
int j_ = j; //不改变挡板位置
//后缀与前缀进行比较
for (m = 1; m <= k && j_ < i; m++, j_++)
{
//字符不同则跳出循环，移动挡板位置（缩小前后缀长度）重新比较
if (t[j_] != t[m])
{
flag = 0;
break;
}
}
if (flag) break;
}
//循环结束时，由于for循环种“m++”实际匹配的最长公共前后缀为m-1；
next[i] = m; //从最长公共前后缀下一位继续匹配，即 m-1+1=m
}
看下来我们会发现next数组的求解与文本串没有关系，任何模式串都可以求出自己的next数组
比较字符串
其实next数组求解完了，比较字符串就很简单了。
先定义i和j两个指针：i指向文本串；j指向模式串。
第一次仍是逐一比较，相同则i、j均右移一位。当出现失配时，i不右移也不回溯，j根据next[j]的值移动，让移动后的模式串继续与第i位匹配比较。
（当指针j回退至0时，指针i、j需同时++。即若主串的第i个字符和模式的第1个字符不等，应从主串的第i+1个字符重新匹配）
循环结束后根据i、j指针位置即可判断
void cal_KMP()
{
cal_nextValue();
if (tempstr.size() < compstr.size())
return;
int i = 1;
int j = 1;
while (i < tempstr.size() && j < compstr.size())
{
if ((tempstr[i] != compstr[j]) && next[j] != 0)
j = next[j];
else
{
i++;
j++;
}
}
if (j == compstr.size()) //匹配成功
{
result.didhave = true;
result.pos = i + 1 - (compstr.size()-1);
}
else if (i == tempstr.size() && j != compstr.size()) //匹配失败
{
result.didhave = false;
result.pos = -1;
}
}
教材简洁版
当我自己摸索完去看了眼教材，发现上面求next数组的程序好短
void get_next(SString T, int next[]){
//T位模式串
i = 1;
next[1] = 0;
j = 0;
while(i < T[0]){
if(j == 0 || T[i] == T[j]){
++i;
++j;
next[i] = j;
}
else j = next[j];
}
}
T[0]应该是存放字符串长度的
有一说一我脑子不好挺难看懂。。放着有大佬会的也可以说说
