BF算法引导
BF算法是一个暴力的字符串匹配算法，时间复杂度是o（m*n）
假设主串和子串分别为
我们想要找到子串在主串的位置
BF算法核心：BF算法就是同时遍历子串和主串，如果不相同就将子串指针回退到首位，主串指针回退到这次遍历的起点的下一个位置
我们指定主串的指针为i，子串的指针为j，如下图：
BF算法步骤（图片演示）
匹配的过程，我将用图来阐释：
1.第一趟
i++;
j++;
i++;
j++;
这时我们发现，i和j指向的内容不一样了
这时我们进入下一趟
2.第二趟
i=i-j+1;
(这里就是主串指针回退到这次遍历的起点的下一个位置，因为每次都是i和j同时走，但j每次都是从0开始走，j同时记录了i每次走了多少步，i-j就是回退到这一趟的起点，但这个起点我们试过了，就是+1，从下一个位置开始试)
j=0;
这里我们发现，i和j指向的内容不一样了
这时我们进入下一趟
3.第三趟
i=i-j+1;
j=0;
i++;
j++;
i++;
j++;
这里我们发现，i和j指向的内容不一样了
这时我们进入下一趟
4.第四趟
i=i-j+1;
j=0;
这里我们发现，i和j指向的内容不一样了
这时我们进入下一趟
5.第五趟
i=i-j+1;
j=0;
这里我们发现，i和j指向的内容不一样了
这时我们进入下一趟
6.第六趟
i=i-j+1;
j=0;
i++;
j++;
i++;
j++;
i++;
j++;
i++;
j++;
这时我们发现主串和子串都遍历结束（这个例子有点奇怪，一般只有一个遍历结束，整个程序就能判断是否有子串，并找到子串位置）
我们不难发现只有当子串遍历完，才能说明主串有这个子串
代码演示
public class BF { static int Bf(String S,String s){ //空字符串 if(S==null||s==null){ return -1; } //主串长度 int SUM=S.length(); //子串长度 int sum=s.length(); //字符串长度为0 if(SUM==0||sum==0){ return -1; } //指针 int i=0; int j=0; while (i<SUM&&j<sum){ if(S.charAt(i)==s.charAt(j)){ i++; j++; }else { i=i-j+1; j=0; } } if(j>=sum){ return i-j; } return -1; } public static void main(String[] args) { System.out.println(Bf("aacascscc","ac")); } }
KMP算法
KMP也是一种字符串匹配算法，只不过他利用了遍历过的串的信息，减少了趟数，最重要就是理解他怎么利用信息
举个例子
我们指定主串的指针为i，子串的指针为j，如下图：
i++；
j++;
一直到匹配不正确的地方
我们想让I指针停下来，只移动j指针，（这是我们想的就是这时i要回退，我们不想让他回退，但又不能丢下前面的，所以我们看前面还有什么能用上的）这时，我们遍历了主串的ABAB ,和子串的ABAB，他们两个肯定是相同的因为刚刚遍历了，如果不相同肯定会停下来，如果是BF算法我们肯定会i=i-j+1;j++;但现在我们想利用我们遍历过的ABAB的信息，我的方法是向后拖拽子串，只要发生拖拽，主串的开头A和子串结尾的B肯定是用不上了，我们必须求的是主串的（从后面开始，如果是从BAB开始算前缀即使前面匹配后面不匹配也没有用）后缀和子串的（从前面开始）前缀，（这里就是为什么求主串的后缀和子串的前缀）
拖拽两次，我们发现主串和子串有AB重叠，这时我们就能继续遍历了（我的思考是这里我们利用了ABAB重叠的信息，省去了i指针回退到主串的下标为2，子串下标为0的地方一点点++匹配，而主串前面AB我们发现没有匹配，所以就丢弃）
现在我们想知道怎么利用匹配过的信息，怎么一下就能找到拖拽后j到的位置
就要引入next数组，来存储j指针在每个位置匹配失败要回退到哪
推next数组
假设有这样一个字符串
规则如下：
前两个下标为0，1的就是固定的，
从下标为2开始，假设匹配失败了，ab内找以a开头以b结尾，除了本身没有这样的字符串，回退到0，
下标为3时，假设匹配失败了，aba内找以a开头以a结尾，有这样的字符串，回退到1，
下标为3时，假设匹配失败了，abab内找以a开头以b结尾，有这样的字符串，回退到2，
后面的自行计算，结果为
给个例题，请求出他的next数组：
接下来我们进行一个推理
设原字符数组为p【】
如上图所示，next【i】=k，假设p【i】==p【k】如上图所示，那么
p【0】…p【k-1】==p【x】…p【i-1】
又已知k-0i-x得到xi-k
p【0】…p【k-1】==p【i-k】…p【i-1】
又因为p【i】==p【k】所以p【0】…p【k】==p【i-k】…p【i】
所以next【i+1】==k+1
推出来的意思是p【8】这个前面有abc和前面的abc匹配p【3】和p【8】又相等那么p【9】找前面的匹配时直接p【8】前面找到的abc加p【8】；
如上图所示，next【i】=k，假设p【i】！=p【k】如上图所示，那么
不是我们要找的，我们就再回退到k=0这时p【i】==p【k】
这时我们又能用next【i+1】==k+1，next【6】=k+1=1
代码演示
public class KMP { public static void main(String[] args) { System.out.println(KMP("CSA","SA")); } public static int KMP (String s, String sub){ int lens = s.length(), lensub = sub.length(); int[] next = new int[lensub]; //next数组 存放匹配不上的子串要跳跃的下标 getNext(next, sub); int i = 0, j = 0; // i 遍历主串， j 遍历子串 while (i < lens && j < lensub) { if (j == -1 || s.charAt(i) == sub.charAt(j)) { i++; j++;//逐一比较，相同的看下一个 //当子串的第一个字符就与主串的字符不相等时，j++为0，i向后移动一位 } else { j = next[j]; } } if (j == lensub) { return i - j; //上面while循环结束条件是因为 遍历发现子串所有均与主串相等 } else { return -1; } } public static void getNext ( int[] next, String sub){ next[0] = -1; next[1] = 0; //固定 int i = 2;//i表示当前所求next数组的下标 int k = 0;//比较是否相等的前一项 while (i < sub.length()) { if (k == -1 || sub.charAt(i - 1) == sub.charAt(k)) { //就是一直回退直到就是说没有利用的重叠部分就是k=-1 next[i] = k + 1;//当k==-1时，证明【0】与【j-1】里无相等字符，k++为0，i移向下一位 k++; i++; } else { k = next[k]; } } } }
之后如果有新的想法会及时补充，大家如果有不同见解欢迎评论区留言
