KMP算法：根据三位作者(D.E.Knuth，J.H.Morris和V.R.Pratt)名字来命名，全称是KnuthMorrisPratt算法，简称为KMP算法。
KMP算法核心思想：假设主串是a，模式串是b，在模式串与主串匹配的过程中，当遇到不可匹配的字符的时候，我们希望通过某种规律可以将模式串往后多滑动几位，跳过那些肯定匹配不上的情况，说白了就是高效关键字搜索。
在模式串和主串匹配的过程中，明确两个概念：
1、好前缀：把已经匹配的那段字符叫作好前缀
2、坏字符：把不能匹配的那个字符叫作坏字符
在模式串匹配主串的过程中，如果遇到了坏字符，我们就需要把模式串向后滑动，滑动过程中，当模式串和好前缀存在上下对应重合，对于前面几个字符的比较，就相当于使用好前缀的后缀子串跟模式串的前缀子串进行比较！这个比较能否更加高效？
KMP算法就是寻找一种规律：在模式串和主串匹配的过程中，当遇到坏字符后，对于已经比对过的好前缀，可不可以寻找一种规律将模式串一次性滑动很多位？
解决方法只需拿到好前缀本身，然后在好前缀的所有后缀子串中，查找到最长的并且跟好前缀的前缀子串还要匹配的子串(最长可匹配后缀子串)。
最长可匹配后缀子串：在好前缀的所有后缀子串中，最长的可以匹配前缀子串的那个后缀子串，叫作最长可匹配后缀子串。
最长可匹配前缀子串：与最长可匹配后缀子串对应，叫最长可匹配前缀子串。
图解：如果最长的可匹配的前缀子串是{v}，长度是k，模式串一次性向后滑动j-k位，也就是在j的基础上减去了j-k，相当于每次遇到坏字符的时候就把j更新为k，i不发生变化，接着继续比较！
BF算法（BruteForce）:暴力匹配算法，如果在字符串A中查找字符串B，那字符串A就是主串，字符串B就是模式串，主串记长度作n，模式串长度记作m，nm，在主串中检查位置分别是0,1,2,3,4...n-m，一共匹配n-m+1次，也就是一共匹配n-m+1个子串。
暴力匹配过程图解：
第一步：主串和模式串匹配位置初始化
第二步：挨个匹配，判断i和j指向的字符是否相等
第三步：如果i和j指向的字符不匹配，i向后移动一位，j重新设为0
程序实现：
intBF(strings1,strings2){//第一步：i和j进行初始化操作inti=0;//主串位置intj=0;//模式串位置//第二步：挨个匹配while(is1.length()js2.length()){//第三步：如果i和j指向d嗯字符相等，那么i和j都向后移动一位，如果i和j指向的字符不相等，i减去j，然后再加1，j重新从0开始if(s1[i]==s2[j]){i++;j++;}else{i=i-j+1//i-j：表示重新回到开始位置，然后加1，表示遇到坏字符向后挪一个位置继续匹配j=0;}}if(j==s2.length()){//j从零开始，如果等于模式串长度，说明匹配完成returni-j;}else{return-1;}}
每次遇到不匹配字符，i指针就要回溯回去，效率明显很低。是否可以利用已经匹配的部分，保持i指针不回溯，通过修改j指针，让模式串移动到一个有效位置？当某一个字符与主串不匹配时，j指针应该移动到哪？
例如，当字符C和D不匹配时：
因为在前面有相同的A匹配，所以j移动到1的位置
再举例，如图：
j移动到2的位置，因为前面已经有两个字符匹配
每一个位置都有可能发生不匹配，也就是每一个j位置都对应一个下次j指向位置k，在这里使用next数组保存，next[j]=k，表示当主串[i]！=模式串[j]时，j指针应该指向的下一个位置值。
当j=0时，不匹配：
j已经在最左边了，不可能再移动了，此刻应该让i指针左移，j相当于减少一个位置，j从0回溯到-1，所以next[0]=-1，一种理解方式，主要为了防止出现死循环k=next[k]，当出现next[0]=-1,说明要回溯到开始位置重新匹配，后面会涉及到。(模式串向右移动，j向左移动)
当j=1时，不匹配：
j指针一定是左移到0位置，前面只有这一个位置
当j=3时，不匹配：
j指针一定是左移到1位置，前面有1个A字符匹配
当j=5时，不匹配：
j指针一定是左移到2位置，前面有2字符AB匹配
规律图解：
总结：当模式串第j个字符和主串第i个字符匹配失败，j要移动到下一个位置k，k前面的字符与k之后到j之间的字符是最长公共前后缀，P是模式串，公式P[0~k-1]==P[j-k~j-1]。
证明：j为什么可以直接移动到k的位置？
当T[i]！=P[j]时：
第一步：当T和P有公共前后缀时，T[i]!=P[j]，T[i-j~i-1]==P[0~j-1]
第二步：当T和P有公共前后缀时，模式串P满足P[0~k-1]==P[j-k~j-1]
第三步：当j==k时，根据①②仍然满足T[i-k~i-1]==P[0~k-1]
总结：当T[i]!=P[j]时，如果最长公共前后缀的长度为k，则下次匹配指针j可以移动到第k位，next[j]=k，这里是以下标为0作为基准。
第一种情况，next[j]数组求解：
P[j]=P[k]时，next[j]=k，则next[j+1]=k+1=next[j]+1;
第二种情况，next[j]数组求解：
P[j]!=P[k]，指针k应该回溯到next[k]位置，k=next[k]
next数组实现分析：
因为需要找出最长公共前后缀，所以开始比较肯定需要错位比较，j指针控制上面的模式串p，k指针控制下面的模式串p。
换种思路理解，为什么可以把主串和模式串的比较转换成模式串和模式串的错位比较？
在匹配过程中，我们始终都是在找相同，遇到不匹配，最长公共前后缀到达极限，上面已经证明了最长公共前后缀的有效性，可以提高效率，就有匹配问题，转换成了对模式串下手，求模式串的最长匹配前后缀问题。
voidgetNext(strings1,intnext[]){intj=0;//负责上面模式串intk=-1;//负责下面模式串next[0]=-1;//j==0,k=-1,next[j]=k,意味着重新开始匹配while(js1.length()-1){if(k==-1
s1[j]==s1[k]){//如果k==-1，也就是意味着下面模式串要重新开始匹配主串（其实还是匹配自己）//算的是下一项前面的最大公共前后缀next[j+1]=k+1;//如果p[j]==p[k]，next[j+1]=next[j]+1，满足上面的第一种情况推导k++;j++;}else{//如果p[j]!=p[k],k应该指向下一个位置，也就是回溯，下一个位置值又提前存储在当前k指向next[k]，所以只需要把k赋值为next[k]，下一次继续拿着当前k指向的next[k]，去向前移动让k指向新的值,k=next[next[k]]。k=next[k];//终归来说都是在假设已经存在最长公共前后缀时，当前k和j指向的值不匹配，规律推导。}}}
next数组优化：
假设P为模式串，T为主串，当T[i]！=P[j]，会存在模式串指针j不能一次性回溯到位的情况，如下图：
按照next数组求解方法，j应该回溯到下标1的位置，但是回溯之后，仍然出现T[i]!=P[j]，因为P[j]==P[next[j]]，所以应该让j直接回溯到0位置，也就是继续回溯到next[1]=0。
优化后程序：
voidgetNext(strings1,intnext[]){intj=0;//负责上面模式串intk=-1;//负责下面模式串next[0]=-1;//j==0,k=-1,next[j]=k,意味着重新开始匹配while(js1.length()-1){if(k==-1
s1[j]==s1[k]){//如果k==-1，也就是意味着下面模式串要重新开始匹配主串（其实还是匹配自己）k++;j++;if(s1[j]==s1[k]){next[j]=next[k];//k的next[k]表示多向前推进一步}else{next[j]=k;}}else{//如果p[j]!=p[k],k应该指向下一个位置，也就是回溯，下一个位置值又提前存储在当前k指向next[k]，所以只需要把k赋值为next[k]，下一次继续拿着当前k指向的next[k]，去向前移动让k指向新的值,k=next[next[k]]。k=next[k];//终归来说都是在假设已经存在最长公共前后缀时，当前k和j指向的值不匹配，规律推导。}}}
KMP算法程序：
intKMP(strings1,strings2){inti=0;//主串的开始下标intj=0;//模式串的开始下标while(is1.length()js2.length()){if(j==-1
s1[i]==s2[j]){//当j为-1时，要移动的是i,j也要归0i++;j++;}else{//i=i-j+1;与暴力匹配最大的不同，去就是i不需要回溯了j=next[j]//j回到指定位置}}if(j==s2.length()){returni-j;}else{return-1;}}一只小跃跃