3358www.Sina.com/(string )是一个由至少零个字符组成的有限序列。 如下图所示
串
一. BF算法
二. KMP算法
一.前缀、后缀、最大公共前缀
二、研究KMP和BF的差异(主要是回溯) )。
三. next序列描述
j位置的确定(即next数组的详细解) ) ) ) ) ) ) ) )。
如果n=0，则为空白字符串，与空白字符串不同。
由字符串中任意连续字符组成的子列(包括空字符串)即为字符串的子列。 子串的概念与数学中的集合相似，如下图所示有cxdsb串
目录
虽然省略了具体的初始化、创建等，但在实际开发中无法隐含地遵守规则。 重要的是学习两种算法
http://www.Sina.com/http://www.Sina.com /
ffdst开始S[0]！=T[0]，因为也同样满足条件，所以S[s]！=T[t]，回溯成立。 循环这个步骤的条件是s，t都比串长小
图来自于bilibili王卓老师
代码按以下方式实现： 以字符数组为例主要给出了算法)
char S[7]={'abcacbb'}； char T[4]={'cacb'}； int s=0； int t=0； while(ssizeof(s ) t sizeof(T ) t ) )/j的范围在主字符串中，t的范围在子字符串中if(s(s )=t (t ) ) ) s； t； //如果值相等，则下一个元素(else ) s=s-t1； //回溯子字符串主字符串t=0； ) if(t )=='/0 ' ) ) {return 1； //找到了}else {return 0； ///循环还没完成}} 一、BF算法KMP算法主要在回溯方面进行了优化，避免了傻瓜式回溯跑到顶。 重要的是找到最大前缀以减少浪费的过程。
由于网上的讲解很多，所以我这一部分主要分为3358www.Sina.com/和此算法也称为简单匹配算法。实际上即是暴力穷举法，算法时间复杂度为O（n*m）,为方便理解算法先看下面图解两部分进行说明。 我的这一部分总结为以下步骤。
当前面元素都满足条件S[s]==T[t]，且进行到T[t]=="/0"时，代表匹配到了字符。此算法每次都要回溯因此时间复杂度为0（n*m）
前缀、后缀、最大公共前缀的概念
研究KMP和BF的差异(主要是回溯) )。
next序列的说明
二、KMP算法前缀的概念照原样看以下例子，比看例子理解要快。 在这里不需要考虑原理什么的。 需要使用这三个概念。 作为平时的知识，
这些字符串包括
“abcde”前缀的集合：{a,ab,abc,abcd}
后缀的集合：{e,de,cde,bcde}
公共缀：就是该字符串 前缀后缀都包含的元素如下图所示
最大公共前后缀：如图中所示字符串“a b c a b d a”有 公共的前后缀为 a,b,ab三种情况，但最大的公共前后缀 就为ab.
失配位：即不相等时的位置。
那么最大公共前后缀有什么意义呢？接下来就进入正题。（本段思路来自天勤考研）
我们设定主串为 S[11]={"abcabbbabc"},子串为 T[5]={"abcabc"}，i，j分别为数组下标
如下图所示，S[i] 与 T[j] 分别对应，直到 i=j=5时，即第六个元素时，二者不相等
当遇到不相等的情况是，BF的算法是将i回溯到 i-j+1 的位置，即之前比较的后一个位置
然而对于Kmp算法则不同，Kmp首先找到主串与子串相同的部分的最大公共前后缀，
其次将子串的前缀挪到与主串后缀的地方对齐。再进行S[i] 与 T[j] 的比较。
总结：步骤为 ①找到 失配位 ② 找到最大公共前后缀
二、研究KMP与BF的区别 （主要是回溯）那么为什么可以直接跳过这些元素而直接比较呢，即为什么 i 可以不回溯，j回溯位置也不用从头开始呢。那么接下来就进行此步骤的剖析：
当遇到不相等元素时证明主串与子串在此元素之前一定都相等。那么先看相等这一部分，如图所示，若子串向右移动，不管移动多少次，子串头元素a只有遇到后缀a时才会相等。那么同理b也是，因此我们直接找到最大公共前后缀，进行对齐即可。这里的移动只是方便看图，实际上移动的 只有 j 。这里的最大公共前后缀是在失配位之前寻找，（即绿线之前）
由此步骤我们得出代码如下所示
图片来自bilibili kddmz老师
BF算法在本文上面有提到，那么Kmp算法与其不同的地方主要在于判定条件，与回溯两处。此处判定条件 j=-1 会越界因此要加上条件，具体在后面会有讲到。j=next[j] 是 j 的回溯条件，即如何确定 S[i] 与 T[j] 不相等时，j 的回溯位置 ！！！再此强调 i 是不用回溯的，敌动我不动即可。只有在匹配成功后才会和 j 一同跳到下一个位置。
三、next数组的讲解那么以上所有步骤，就是Kmp算法的整体架构，接下来我们只需要考虑 next 数组了，同时这里也是最关键的地方 ！！！
next数组的意义在于找到每次 S[i] 与 T[j] 不相等时，即失配位时，j 的回溯位置 ， 这里我们先以手算法，讲解以便于理解后面的代码部分
事实上，在我们“移动”的过程中，根本不需要看主串，只需要看 子串（模式串）即可，直接将字串的最大前缀移动到最大后缀出即可如下图所示。此时我们再此强调，所谓的移动指示假想的，实际上是 j 的移动，如图 j 从原来失配位移动到了后缀之后。
j 位置的确定 （即next数组的详解）一、手算图解法
此法仅仅为了方便观察对应代码来思考方便理解。（这里我们用新的一组子串来演示）
由上图可知，想要判断最大公共前后缀只需要子串即可，那么我们制作以下表格
这里的 T 代表了子串（模式串）后面数值为 子串内容，下标为串数组对应下标，next即为 j 要回溯的位置。
注意：这里next不同视频教程，有不同的版本，大概讲解一下，其实就是各个位右移的区别。
本文采用第二种方式 （这里不懂下面讲）
next数组的求法
第一步：数组初始化：
我们设定 j 为前缀 i 为后缀 。数组初始化 j 就等于0，对应的数组元素就等于 a，i为后缀所以 i=3,此时的 j 对应的 next值即为 -1.这里可以是0，也可以是-1，对应的上面的表，那么数组外部的 j=next [] =-1; 此时就对应之前的判断条件，为什么要加上j=-1。
第二步：求next [ j ]的值
求法是前n项 是否有公共前后缀，没有填0，有一个则填1，有两个填2，以此类推
当 j =-0时，数组初始化， next [1] = -1；
当 j =1 时，前面就只有a一个元素，所以 next [1] 应该为 0；
当 j =2 时，前面有a b 两个元素， 所以 next [2] 应该为 0；
当 j =3 时，前面有a b a 三个元素，所以 next [3] 应该为 1；（有公共前后缀 a）
后面以此类推，结果如下表
二、代码解法
将图表和代码结合看
总结：j 始终指向 a的位置，移动的为 i ，当遇到 j==-1 或 T [ i]=T [ j ]时才会+1，进行下一元素比较，如果相等其实是代表了最大公共前后缀有2位，若不相等，则证明只有一位最大公共前后缀，与此同时，j=next[ j ],也就是回退到值等于a的地方。