• 🙋 个人网站: 路遥叶子
• 🤟 版权: 本文由【路遥叶子】原创、在CSDN首发、需要转载请联系博主
• 💖如果文章对你有帮助、欢迎关注、点赞、收藏(一键三连)和订阅专栏哦
• 💅 想寻找共同成长的小伙伴，请点击【Java全栈开发社区】

目录

 ​​​带你详细了解KMP算法！

🐋 🐋 Brute-Force算法和KMP算法有什么区别？

 🐋 🐋KMP算法的详细讲解：

🍀🍀🍀 求公共前后缀 next 数组-- 推导🍀 🍀🍀

🍀🍀🍀 求 next[ j ]函数算法🍀 🍀🍀

 🎃🎃 算法分析 ：

🍀🍀🍀 模式匹配的KMP算法🍀 🍀🍀

 🎃🎃 算法分析 ：

如果觉得文章对您有帮助，就拿起你的小手赶紧给博主点赞、评论、收藏一下吧~~~ 赶紧动起来，让我们一起加油学习。博主会不断推出更多优质文章哟

 ​​​带你详细了解KMP算法！

​

🐋 🐋 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-模式串的长度，就是首位置    }}

🎃🎃 算法分析 ：

​

​

​

自此我们对KMP的讲解到处结束啦！你理解了吗？

​

如果觉得文章对您有帮助，就拿起你的小手赶紧给博主点赞、评论、收藏一下吧~~~ 赶紧动起来，让我们一起加油学习。博主会不断推出更多优质文章哟

​