理解KMP算法

悠悠 2022-10-15 04:52 206阅读 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/