理解KMP算法 悠悠 2022-10-15 04:52 129阅读 0赞 > 总结不易,如果对你有帮助,请点赞关注支持一下 > 微信搜索**程序dunk**,关注公众号,获取博主的数据结构与算法的代码笔记 ### 目录 ### * KMP * * KMP算法介绍 * * BF(Brute Force) * KMP算法 * * 计算next数组 * 为什么要进行next回溯 * \[28. 实现 strStr()\](https://leetcode-cn.com/problems/implement-strstr/) # KMP # ## KMP算法介绍 ## > 它主要的用途就是查找字符串,查找字符串"ab"(目标字符串)在字符串"abc"(待查找字符串)中出现的位置。换句话说,就是查找字符串"abc"是否包含字符串"ab",如果包含,返回包含的起始位置 算法由两部分组成 1、计算subStr每一位及之前的字符串中,前缀和后缀公共部分的最大长度的next数组 2、匹配destStr和subStr,当subStr失配时,利用next数组,实现subStr的最大后移,从而避免不必要的匹配,减少匹配次数 ### BF(Brute Force) ### ![BF算法][BF] class Solution { public int strStr(String haystack, String needle) { int len1 = haystack.length(); int len2 = needle.length(); if(len2 == 0) return 0; int l = 0; int r = 0; while(l < len1 && r < len2) { if(haystack.charAt(l) == needle.charAt(r)) { l++; r++; } else { l = l - r + 1; r = 0; } } if(r == len2) { return l - r; } return -1; } } ### KMP算法 ### ![KMP算法][KMP] ![image-20210420180546175][] #### 计算next数组 #### private static int[] getNext(String target) { //创建一个数组 int[] next = new int[target.length()]; //定义两个变量 int len = -1;//指向当前公共前缀的前端的末尾 int y = 0;//指向当前公共前缀的后端的末尾 //赋初值 next[0] = -1; while(y < target.length() - 1) { if (len == -1 || target.charAt(len) == target.charAt(y)) { len++; y++; next[y] = len; } else { len = next[len]; } } return next; } #### 为什么要进行next回溯 #### ![image-20210420181035587][] ![image-20210420181043866][] ## [28. 实现 strStr()][28. _ strStr] ## > 实现 strStr() 函数。 > > 给你两个字符串 haystack 和 needle ,请你在 haystack 字符串中找出 needle 字符串出现的第一个位置(下标从 0 开始)。如果不存在,则返回 -1 。 > > 说明: > > 当 needle 是空字符串时,我们应当返回什么值呢?这是一个在面试中很好的问题。 > > 对于本题而言,当 needle 是空字符串时我们应当返回 0 。这与 C 语言的 strstr() 以及 Java 的 indexOf() 定义相符。 示例 1: 输入:haystack = "hello", needle = "ll" 输出:2 示例 2: 输入:haystack = "aaaaa", needle = "bba" 输出:-1 class Solution { public int strStr(String haystack, String needle) { if(needle.length() == 0) return 0; return kmpSearch(haystack, needle); } public int kmpSearch(String haystack, String needle) { int[] next = getNext(needle); int x = 0; int y = 0; while(x < haystack.length() && y < needle.length()) { if(y == -1 || haystack.charAt(x) == needle.charAt(y)) { x++; y++; } else { y = next[y]; } } if(y == needle.length()) { return x - y; } return -1; } public int[] getNext(String needle) { int[] next = new int[needle.length()]; int len = -1; int y = 0; next[0] = -1; while(y < needle.length() - 1) { if(len == -1 || needle.charAt(len) == needle.charAt(y)) { len++; y++; next[y] = len; } else { len = next[len]; } } return next; } } [BF]: /images/20221014/d0a67f18b196425f81d892066a875317.png [KMP]: /images/20221014/e1b643c76a0d417a990ff9b5d70a5bfe.png [image-20210420180546175]: /images/20221014/2c4d492f18854b16977325e653bf23de.png [image-20210420181035587]: /images/20221014/f2e5ee0966ed4c0cabcbed6b2ed2f654.png [image-20210420181043866]: /images/20221014/ec58bc5376e545358c18968ca97beb15.png [28. _ strStr]: https://leetcode-cn.com/problems/implement-strstr/
还没有评论,来说两句吧...