本文共 2757 字，大约阅读时间需要 9 分钟。

BF算法

算法思想：

比较简单，定义i，和j分别指向主串和字串的头部），依次向后比较，若比较失败，主串和字串都需要回溯（i=比较轮数+1的位置，j回到0位置） 元素相同，故i，j均向后移一位 元素不同，i退回第二个位置。j变成0 元素还是不同，i退到第三个位置 结束

#include
   
    #include
    
     bool BF(char a[],char b[]){	int index1 = 0;//指向a的头部 	int index2 = 0;//指向b的头部 	for(int i = 0;i
    
   

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
   
    #include
    
     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
     
    
   

这里很难理解的点是

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，现在后缀多了一个元素，去判断公共部分以外的第一个元素是否与这个元素重合），否则我们进行回溯，直到找到一个新的（更小的）公共部分

转载地址：http://jgqen.baihongyu.com/