Brute-Force算法和KMP算法有什么区别？
🍁🍁🍁 Brute-Force算法：蛮力算法，依次比较每一个，比较次数多，时间复杂度O(n×m)。
🍁🍁🍁 KMP算法：滑动算法，比较的次数较少，时间复杂度O(n+m)。
🌲🌲🌲🌲🌲🌲🌲🌲🌲🌲🌲🌲🌲🌲🌲🌲
🍀🍀 🍀🍀注：根本区别在于，主串指针 “ i ” 是否回退。🍀🍀🍀🍀
🍁🍁🍁 Brute-Force算法：每次对比匹配不成功时，主串指针" i "都会进行 回退。
🍁🍁🍁KMP算法：每次对比匹配不成功时，" i "指针不回退，而是利用已经得到的“部分匹配”的结果，将模式向右“滑动”，尽可能远的一段距离后进行比较。
🐋 🐋KMP算法的详细讲解：
🍀🍀🍀 求公共前后缀 next 数组-- 推导🍀 🍀🍀
🎃🎃 公共前后缀, 指的就是主串和模式串具有相同的内容，所以只需要看模式串前后所具有的公共前后缀。【原因：我们的目的是让模式串在主串中进行全部匹配成功，那么在已经匹配成功的部分串中，主串和模式串的内容都是一样的。因此只需看模式串的公共前后缀】
🎃🎃next[ ] 数组的作用：
一是：next[ i ]的值，表示下标为i 的字符前的字符串最长相等前后缀的长度。
二是：表示该处字符不匹配时应该回溯到的字符的下标
🎃🎃实例1：
模式串："abcabc"
❄️❄️❄️next[ ] 数组：
默认前两个位置
第一个位置：-1
第二个位置：0
原因：
第三个位置：0
第四个位置：0
第五个位置：1
第六个位置：2
🍀🍀🍀 求 next[ j ]函数算法🍀 🍀🍀
/** * 获得next数组 * @param T 模式串 * @return 返回next数组 */ public int[] getNext (IString T) { int[] next = new int[T.length()]; //创建next[] 数组，与模式串字符个数一致 int j = 1 ; //主串指针 int k = 0 ; // 模式串指针(相同字符计数器) //2. 默认情况 next[0] = -1 ; next[1] = 0 ; //3. 准备比较 while (j < T.length() -1) { //比较倒数第二个字符 if (T.charAt(j) == T.charAt(k)) { //匹配，连续有字符相等 next[j+1] = k+1 ; j++ ; k++ ; }else if (k == 0 ) { //失配 next[j+1] = 0 ; j++ ; }else { // k不是0 k = next[k] ; } } //4 处理完成，返回数组 return next ; }
算法分析 ：
例1：模式串abcabc
例2：模式串ababaaa
🍀🍀🍀 模式匹配的KMP算法🍀 🍀🍀
/** * @param T 模式串 * @param start 在主串中的开始位置，例如："ababababaaa".indexKMP("ababaaa", 0); */ public int index_KMP(IString T, int start) { int[] next = getNext(T); // 根据模式串获得next数组 int i = start; // 主串指针，从start开始 int j = 0; // 模式串指针 //字符比较 while(i<this.length() && j < T.length()) { //指针不能超过串 // j==-1 表示第一个字符不匹配，i移动到下一个，j从0开始 if(j==-1 || this.charAt(i) == T.charAt(j)) { i++; j++; } else { //某一个字符不匹配，i不变，移动j的位置 j = next [j]; } } //返回结果 if(j< T.length()) { return -1; //j小于模式串的长度，表示没有匹配上 } else { return i - T.length(); //如果匹配上，i-模式串的长度，就是首位置 } }
算法分析 ：
