BF算法
算法思想：
比较简单，定义i，和j分别指向主串和字串的头部），依次向后比较，若比较失败，主串和字串都需要回溯（i=比较轮数+1的位置，j回到0位置）
元素相同，故i，j均向后移一位
元素不同，i退回第二个位置。j变成0
元素还是不同，i退到第三个位置
结束
#include<stdio.h>
#include<string.h>
bool BF(char a[],char b[]){
int index1 = 0;//指向a的头部
int index2 = 0;//指向b的头部
for(int i = 0;i<strlen(a);i++){//轮数
if(a[index1]==b[index2]){
index1++;
index2++;
}else{
index1 = i+1;
index2 = 0;
}
if(index2==strlen(b)) return true;
}
return false;
}
int main(){
char a[6] = {'a','c','a','b','d','a'};
char b[3] = {'a','b','d'};
char c[3] = {'a','b','e'};
if(BF(a,b))printf("匹配\n");
else printf("不匹配\n");
if(BF(a,c))printf("匹配\n");
else printf("不匹配\n");
return 0;
}
KMP算法
BF算法的弊端：
每次j下标都要回到0号下标，当主串和字串匹配失败时，主串进行回溯会影响效率，回溯之后，主串与字串有些部分比较是没有必要的
以下图为例，当i=j=5的时候匹配失败
按照BF算法，i=1，j=0，但这显然是多余的，因为子串第一个字符是A，令主串指针回溯到B的位置没有必要
（主串前六个字符我们都是访问过的），只需要令i=3，j=0就可以继续比较了。
更进一步，子串第二个字符是B，而i=4刚好指向B，那么可以令i = 4，j = 1
同理可以令i = 5，j = 2
我们发现i和最初没有变化，只有j的位置变化了
整个KMP的重点就在于当某一个字符与主串不匹配时，我们应该知道j指针要移动到哪
事先我们会计算每个字串【0，k】的前缀和后缀公共部分的最大长度，信息保存在next数组中。一旦匹配失败，就调取这个子串【0，i-1】的next数组信息（假设i下标时匹配失败），j移动
因为这个重叠部分之前已经比较过了，不用再次比较
算法实现
next数组
next数组是字符串每一位及之前的字符串中，前缀和后缀公共部分的最大长度的集合
next[i]储存的是string中前i+1位字符串前缀和后缀的最长长度
比如ptr字符串(abxabwabxad)，那么next数组就有11个元素
next[0]=-1（无前后缀）
next[1]=0（ab无公共前后缀）
next[2]=0(abx中无公共前后缀)
next[3]=1(abxa公共前后缀最长为a，长度为1)
next[4]=2(abxab公共前后缀最长为ab，长度为2)
next[5]=0(abxabw中无公共前后缀)
next[6]=1(abxabwa公共前后缀最长为a，长度为1)
next[7]=2(abxabwab公共前后缀最长为ab，长度为2)
next[8]=3(abxabwabx公共前后缀最长为abx，长度为3)
next[9]=4(abxabwabxa公共前后缀最长为abxa，长度为4)
next[10]=0(abxabwabxad中无公共前后缀)
注：前缀是第一个元素到倒数第二个元素
后缀是第二个元素到倒数第一个元素
next数组求法，是自身与自身的匹配
求next【k】，k=0，1，2，。。。，N
取第一个串的后半部分（int）（k/2）个数
和第二个串前一部分
如求下面一个串的next【6】:这里先不讨论next数组求法，最后再分析
#include<stdio.h>
#include<string.h>
void getNext(char a[],int *next){
next[0]=-1;
int k = -1;
for (int q = 1; q < strlen(a); q++)
{
while (k > -1 && a[k + 1] != a[q])
{
k = next[k];//往前回溯
}
if (a[k + 1] == a[q])//如果相同，k++
{
k = k + 1;
}
next[q] = k;
}
}
bool KMP(char a[],char b[]){
int next[strlen(a)];
getNext(a,next);
int i = 0;
int j = 0;
int len1 = strlen(a);
int len2 = strlen(b);
while(i<len1&&j<len2){
if(a[i]==b[j]||j==-1){ //注意一定要j = -1，前后公共部分长度为0，就没有必要回溯了
i++;
j++;
}else{
j = next[j];
}
}
// printf("%d,%d ",i,j);
if(j==strlen(b)) return true;
return false;
}
int main(){
char a[] = "abacababa";
int next[strlen(a)];
getNext(a,next);
//for(int i = 0;i< strlen(a);i++)printf("%d ",next[i]);
char b[] = "cba";
char c[] = "ca";
char d[] = "baba";
if(KMP(a,b))printf("匹配\n");
else printf("不匹配\n");
if(KMP(a,c))printf("匹配\n");
else printf("不匹配\n");
if(KMP(a,d))printf("匹配\n");
else printf("不匹配\n");
return 0;
}
这里很难理解的点是
while (k > -1 && str[k + 1] != str[q])
{
k = next[k];
}
从代码上看：我们往前找到一个k，使a[k + 1]==a[q]
为什么要找这个：因为要找前后缀的新的公共部分，a[k+1]是前缀的公共部分+1，a[q]是原来后缀的最后一个+1(即新增的元素)
注意；这里的公共部分是上一次求出的，也就是最后一个是a（用递归的思想去理解，我们不关注前面具体怎么来的）
为什么要回溯：因为匹配不对了–》因此现有的前缀和后缀公共长度是0？
这显然是不对的，你不能保证这个串前缀完全没有能和后缀匹配的部分。
比如这个求next【7】，最后一个数不同，是不是意味着公共长度为0？显然不一定（我怎么知道前面有没有C出现?）
这个时候我们需要回溯到前面找到C
回溯不一定是k–（这样太麻烦，而且据说会出错）
看黄色的部分前缀后缀重叠部分是ABA，长度为3，那么next【k】=2，回溯一次（用于比较的是a【k+1】）
还不同，还需要回溯，现在黄色部分是aba，前后缀重叠部分为a，那么next【k】=0，回溯一次（用于比较的是a【k+1】）
还不同，继续回溯重叠部分为0，那么next【k】=-1；
举一个更明显的例子
虽然不匹配了，但是明显还有公共的部分【a，g】
结合整体代码总结一下
for (int q = 1; q < strlen(a); q++)
{
while (k > -1 && a[k + 1] != a[q])
{
k = next[k];//往前回溯
}
if (a[k + 1] == a[q])//如果相同，k++
{
k = k + 1;
}
next[q] = k;
}
循环求next数组，q是最后一位，而k是前缀的公共部分的最后一个（上一次求出的）的下一个，如果这个数和a【q】相等，那么公共部分长度可以加1（因为原来前缀后缀公共部分长度是K，现在后缀多了一个元素，去判断公共部分以外的第一个元素是否与这个元素重合），否则我们进行回溯，直到找到一个新的（更小的）公共部分