BP&KMP算法
字符串匹配
前言
本文是基于懒猫老师的课程----BP&KMP所写，在观看本文之前最好配合视频或者PPT食用更佳，地址我附在下面：
https://www.bilibili.com/video/BV1EE411378s?spm_id_from=333.788.videopod.sections&vd_source=3daecc9000cbc58a3bc39bf941c4d208
https://www.bilibili.com/video/BV1U7411f7CB?spm_id_from=333.788.videopod.sections&vd_source=3daecc9000cbc58a3bc39bf941c4d208
BP算法（基础）
BF算法的原理
BF算法其实是比较简单的，这两个算法都是用于字符串匹配
比如给定一个主串 S,一个模式串T又称为子串
在子串和主串比较的过程中 每当子串与主串的元素相同时i++，J++,直到出现了不同的元素时，主串和子串的指针进行回溯，主串指针i回溯到i+1（i-j+1）的位置上，子串回溯到0的位置上，其实从图像上看就是子串相对于主串向前移动了一个位置，即从现在主串的新的i位置进行重新匹配，直到匹配成功跳出循环，即循环条件为i！=[\0]&&j！=[\0],结束循环后说明i和j至少有一个到了末尾即遍历完毕，这时候做一个if-else判断即可，成功返回起始下标，否则返回-1即可，
引文
其实我们在观看懒猫老师课上的动画演示以及计算完BF的时间复杂度后，我总感觉很多次比较是没有必要的，从而浪费了很多时间，但事实的确是这样的，这一点后续会给出具体分析，第二就是我们发现每一次匹配不成功时就需要大量回溯，没有利用已经部分匹配的结果
那么我们怎样解决这些问题呢，而下面的KMP算法其实就是BF算法的进阶，它本质上是基于BF算法的思想并借助next数组对代码进行了修改，但却很好的解决了这些问题
KMP算法（进阶）
KMP算法与BF算法最大的不同就是在于“失配”情况的处理，即在遇见字符不匹配时，在KMP算法主串不会进行回溯即保持不变，而子串会向前滑动一段距离，这个滑动的距离怎么确定呢（难点）
首先我们要明确当我们的主串不回溯时，我们既要达成我们匹配字符串的目标，也要尽可能的提高效率（滑动距离的确定），这时我们的子串最多移动到发生失配位置前面而不能移动到失配位置之后（会有遗漏）
我们怎样理解计算滑动距离的公式呢？
已匹配字符数就是失配位置前的字符数量（匹配成功的字符数），最长前缀匹配字符数可以借助PPT来理解，比如这里失配位置之前最长的是ab，长度为2，所以滑动距离就是6-2=4。
算法总结：
这个“滑动”虽然在图像上看着容易，但是当我们的字符串比较长时需要滑动的次数就越来越多，用一个普适性的代码，来实现这个公式以及把握一些细节的处理是比较难的，我们需要用next数组来计算（存储失配位置前）（最长前缀匹配字符数）（重难点），从而帮助我们实现KMP的伪代码，
在大致了解KMP算法的大致思想后 首先我们还是先分析前文提到的问题“对于滑动过程中所略去的字符真的全部都可以不比较吗”
因为我们在准备滑动之前已经比较失配位置了前面的所有字符，例如在下图第二趟中，我们为什么可以不比较a和b呢，因为在第一趟的时候我们知道（主串第二个元素b）=（子串的第二个元素b），即T[1]=S[1]而T[1]!=T[0],则T[0]!=S[1],接下来同理，直到“e”前面的“ab”，因为此时子串的第一个元素发生了重现，即出现了前缀后缀相等的情况，这个时候我们就需要将子串滑动到此处重新执行比较操作，一直这样持续下去。
伪代码描述
next数组递归求解思路
首先我觉得这个算法虽然简短，但是确实很难理解的，需要所谓的数形结合的方式来帮助我们去弄懂，给我的感觉就像是在动态的去解决问题 代码如下：
//next数组
//这个算法其实是比较难以理解的 需要借助图像
void getNext(char *T,int *next)
{
int j=-1;//j代表前缀，i代表后缀
int i=0;
next[0]=-1;
int length= strlen(T);
while (i<length)
{
if(j==-1 ||T[i]==T[j])
{
i++;
j++;
next[i]=j;//
} else{
j=next[j];
}
}
}
算法思路详解
我们得明确next数组到底需要去做什么以及明白它的原理（非常重要）
对于下面的图片中，我们已知A1和A2相等，这里的相等不仅是长度还有值也是相等的，而我们的目的是找到失配位置前的最匹配的前缀后缀长度，那么我们还需要去往后继续比较，看看是不是还相等，那么j在这里表示前缀，i表示后缀，而T[j]正好就表示A1后面的元素，所以我们就还需要比较T[i]和T[j]，
如果相等那么i和j就需要向后移动，此时我们将j的值++后填入我们i++后的位置上，而这时填入的j++后的值就是我们目前找到的最大长度
上面的情况我们分析完毕，我们回到原先的判断语句，如果不相等（难点），那么就是说明A1和A2就【失效】了，我们需要退而求其次，我们需要考虑图中A1,A2之外最长的B1,B2，那么我们的前缀j的位置自然就需要回溯到之前类似的情况，只不过这时候j的前面，我们已知的是B1=B2，B1和B2是作为此时的回溯后j（上一次循环后填入的结果）的前缀后缀出现的，但是由于一开始我们知道A1=A2，而B1和B3都是其各自的子串，那么我们就可以得出B1=B2=B3,那么这时只需要将已知相等的B1和B3进行比较，也就是又返回到了上面一种情况，如此往复，可以说是非常巧妙了
KMP算法实现及测试（先做在看！）
//KMP算法
int KMP (char *S, char *T,int * next)
{
int i=0;
int j=0;
int lenS= strlen(S);
int lenT= strlen(T);
while (i<lenS && j<lenT)
//这里为什么没有用while(S[i] != '\0' && T[j] != '\0')呢，
// 因为 当j为-1的时候数组会发生越界
{
if(j==-1 || S[i]==T[j])
{
i++;
j++;
} else{
j=next[j];
}
}
if(j==lenT)
{
return i-j;
} else{
return -1;
}
}
int main() {
char S[] = "DABASHUASH";
char T[] = "AS";
int result = BP(S, T);
printf("Result: %d\n", result);
int next[10];
getNext(T,next);
int result2= KMP(S,T,next);
printf("Result: %d\n", result2);
return 0;
}