一方面，BF算法暴力匹配(BF )算法是一种普通的模式匹配算法。 BF算法的思想是将目标字符串s的第一个字符与模式字符串t的第一个字符进行匹配，如果相等，则继续比较s的第二个字符和t的第二个字符； 如果不相等，则比较s的第二个字符和t的第一个字符，然后依次比较，直到得到最后的匹配结果。
请看BF的代码实现：
以一系列字符串(S=“abcdefg”，T=”cde”)为例：
intBF(constchar*str，const char *sub，int pos ) ) assert(str！=空子！=空； int i=pos； 用I记录//s中字符的位置int j=0； 用//J记录t中字符的位置的intlens=strlen(str )； intlensub=strlen(sub； 如果//s不为空，且t不为空，则如果每个字符的比较while(jlensubilens ) if ) str ) I )=sub ) I )/s的第I个字符等于t的第j个字符，则I向后一个，j向后一个) j； }如果} else //的第I个字符与t的第I个字符不相等，I返回上一个位置的下一个位置，j返回第0个位置{ i=i-j 1； j=0； }if(j=lensub )/j走了t的长度时，表示t在s中匹配成功({ return i-j； //此时返回主字符串中下标的位置，此时I位于该下标位置j的长度位置，因此返回i-j。 在本例中，如果返回下标3 } //而匹配失败，则返回-1。 -1因为下标不存在，所以不能返回0下标else return -1。 }关于BF算法：
1 .如果第一个字符不同，j也会继续进行后方比较。 例如，如果“a”和“d”不同，则示例中的“abcdefg”和“def”很明显，即使后面的两个字符立即相等，也不是同一子列。
2.j下标每次回0号下标。 如果主字符串和字符串匹配失败，主字符串回溯会影响效率。 回溯后，不需要比较主字符串和字符串的一部分
综上所述：
这种简单丢弃前匹配信息的算法带来了很大的浪费和后匹配效率
2.kmp算法在KMP算法中，针对每个图案列提前计算图案列的内部匹配信息，当匹配失败时最大限度地移动图案列以减少匹配次数，很好地解决了BF算法的缺点
例如，在一致失败的情况下，只要能够使模式字符串尽可能向右偏移，与主字符串一致即可。 向右偏移的距离用KMP算法计算。 在一致的字符串中，找出最长的相同前缀和后缀，使它们重合移动，这个位置就是j返回的位置。 这样的话，j没有必要每次返回到0号的位置，每次j返回的位置被收纳在一个排列中，被称为next
那么j型背包的位置什么是最佳的呢
请看一组图：
根据以上理论，求出图案列的next排列：
代码实现如下所示。
voidgetnext(int*next，const char *sub ) { next[0]=-1； next[1]=0； intlensub=strlen(sub； int i=2； //当前i int k=0； //上一项中的k值while(Ilensub ) if ) k==-1||sub[I-1]==sub[k] ) { next[i]=k 1； I； k=k 1； } else { k=next[k]； }}intkmp(constchar*str，const char *sub，int pos ) ) int pos； int j=0； intlens=strlen(str； intlensub=strlen(sub； int*next=(int* ) malloc ) sizeof(int ) * lensub )； 资产(下一步！=空； 获取下一个(next，sub )； while(jlensubIlens ) if(j=-1|||str[I]==sub[j] ) I； j； } else { j=next[j]； }if(j=lensub ) { return i-j； } else { return -1； }那么，KMP算法可以优化吗？ 请看以下示例：
以字符串“a b a b c”为例，如果第二个a不一致，则一致的字符串一定不是a。 此时，将当前值与字符串的sub[next[i]]值进行比较，如果相同，则将nextval[next[i]]值存储在nextval[i]中，在不同的情况下，将当前值的
以模式列为例，求出他的next值和nextval值。
接下来是代码实现。
(基于next序列，实现KMP的优化)
voidnextval(int*nextval，const char *sub ) { nextval[0]=-1； nextval[1]=0； intlensub=strlen(sub； int i=2； int k=0； int*next=(int* ) malloc ) sizeof(int ) * lensub )； 资产(下一步！=空； 获取下一个(next，sub )； while(Ilensub ) if ) k==-1||sub[I]==sub[next[I] ) { nextval[i]=nextval[next[i]]； I； k=k 1； } else { k=next[i]； }三、从BF算法到KMP算法的时间复杂度优化、更优化是为了实现更优化的代码。 看看这些排序的时间复杂度吧。