学习笔记：KMP算法

今天药忘吃喽~ 2022-10-10 01:51 185阅读 0赞

# KMP算法（理解笔记） #

### 一、前言 ###

本笔记的代码为“leetcode28. 实现 strStr()”所写，因为获取字符串都是从第0位开始，所以和下面的从第一位开始的有所不同。但是大致思路都是一样的。

“天勤”数据结构中的第四章串的部分，详细讲解了KMP算法的过程（都是c语言实现）。如下：

*  串的结构：

typedef struct{ 
        char str[maxSize+1];  //因为多出一个'\0'作为结束标记
        int length;
    }Str;

*  获取next数组的方法：

void getnext(Str substr,int next[]){ 
        int i = 0,j = 0;
        next[1] = 0;
        while(i<substr.length){ 
            if(j==0||substr.ch[i]==substr.ch[j]){ 
                ++i;
                ++j;
                next[i] = j;
            }else{ 
                i = next[j];
            }
        }
    }

*  KMP算法：

int KMP(Str str,String substr,int next[]){ 
        int i = 1,j = 1;
        while(i<=str.length&&j<=substr.length){ 
            if(j==0||substr.ch[i]==substr.ch[j]){ 
                ++i;
                ++j;
            }else{ 
                i = next[j];
            }
        }
        if(j>substr.length){ 
            return i-substr.length;
        }else{ 
            return 0;
        }
    }

注：  
这里书上为了配合讲解，字符都是从位置“1”开始存储。实际应用就得从“0”开始了。  
看视频有人说，很多学校都是从1开始，位置“0”存储数组的长度。（待考证）

### 二、Next数组 ###

1.首先来了解一下，创建next数组的思路流程。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dvYWlsaXFpMTIxMzQ_size_16_color_FFFFFF_t_70]

那么next数组里保存的数字什么意思？

**例：** next\[5\]的适合，求坐标5前面的子串，最长相等前后缀的长度+1就是next\[5\]的值（**最长相等前后缀里的“前缀”的下一个位置，也就是下一个要比较的位置**）。  
这里初始状态设为-1。

2.这里跟着代码走一下：

int getNext(String needle,int next[]){ 
            
            char[] p = needle.toCharArray();
            
            int j = -1;
            int i = 0;
            next[0] = -1;
            while(i<p.length-1){ 
                if(j==-1||p[i]==p[j]){ 
                    i++;
                    j++;
                    next[i] = j;
                }else{ 
                    j = next[j];
                }
            }
    }

第一次循环：i = 0，j = -1，j==-1成立；i= 1，j = 0，**next\[1\]=0**;  
第二次循环：i = 1，j = 0，p\[1\]不等于p\[0\]；**j** = next\[0\] **= -1**;  
第三次循环：i = 1，j = -1，j==-1成立；i= 2，j = 0，**next\[2\]=0**;  
第四次循环：i = 2，j = 0，p\[2\]等于p\[0\]；i= 3，j =1，**next\[3\]=1**;  
第五次循环：i = 3，j = 1，p\[3\]等于p\[1\]；i= 4，j =2，**next\[4\]=2**;  
第六次循环：i = 4，j = 2，p\[4\]等于p\[2\]；i= 5，j = 3，**next\[5\]=3**;  
第七次循环：i = 5，j = 3，p\[5\]等于p\[3\]；i= 6，j = 4，**next\[6\]=4**;

有B站大佬生动的描述这个过程，就像是找门牌。

### 三、KMP原理 ###

**文字原理（来自B站的up主）：**

流程：  
1.求next\[j\],则已知next\[0\]、next\[1\]…next\[j-1\]  
2.假设next\[j-1\] = k1,则有P0…Pk1-1 = Pk1+1…Pj-2(前k1-1位字符与后k1-1位字符重合)  
3.如果Pk1=Pj-1,则P0…Pk1-1Pk1 = Pk1+1…Pj-2Pj-1,则next\[j\]=k1+1,否则进入下一步。  
4.假设next\[k1\]=k2,则有P0…Pk2-1 = Pk1-k2+1…Pk1-1  
5.第二步第三步联合得到：P0…Pk2-1 = Pk1-k2-1 = Pj-k1+1…Pj-k2+1…Pj-2即四段重合。  
6.这时候，再判断如果Pk2=Pj-1,则P0…Pk2-1Pk2 = Pj-k2+1…Pj-2Pj-1,则next\[j\] = k2+1,否则再取next\[k2\] = k3…以此类推。

**文字流程有些难懂，以下是图片讲解：**

以下的图片讲解搬运自B站up主，笔记的最后会标注B站视频链接。  
（注：这个图片讲解是参考前言中的形式，是从位置1开始的。可以理解它的思路）

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dvYWlsaXFpMTIxMzQ_size_16_color_FFFFFF_t_70 1]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dvYWlsaXFpMTIxMzQ_size_16_color_FFFFFF_t_70 2]

这四部分都是重合的。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dvYWlsaXFpMTIxMzQ_size_16_color_FFFFFF_t_70 3]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dvYWlsaXFpMTIxMzQ_size_16_color_FFFFFF_t_70 4]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dvYWlsaXFpMTIxMzQ_size_16_color_FFFFFF_t_70 5]

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dvYWlsaXFpMTIxMzQ_size_16_color_FFFFFF_t_70 6]

还有一种比较容易理解的流程：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dvYWlsaXFpMTIxMzQ_size_16_color_FFFFFF_t_70 7]

### 四、代码实现： ###

（每个人有不同的规则，比如next数组的第一位默认设置值，或者是从第一位开始还是从第0位开始。所以个人觉得，理解了这些思路以后，设计一个自己容易理解的代码思路，以后这种KMP算法就可以套用自己的规则。）

#### 题目要求： ####

> 实现 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

**示例 3：**

输入：haystack = "", needle = ""
    输出：0

**提示：**

>  *  0 <= haystack.length, needle.length <= 5 \*  1 0 4 10^4 104
>  *  `haystack` 和 `needle`仅由小写英文字符组成

#### 代码实现： ####

class Solution { 
        public int strStr(String haystack, String needle) { 
            //字符串转为字符数组
            char[] t = haystack.toCharArray();
            char[] p = needle.toCharArray();
            
            //判空
            if(p.length==0){ 
                return 0;
            }
            //建立next数组
            int[] next = new int[p.length];
            //要和next[0]相同
            int j = -1;
            int i = 0;
            //设置初值为-1
            next[0] = -1;
            while(i<p.length-1){ 
                if(j==-1||p[i]==p[j]){ 
                    i++;
                    j++;
                    next[i] = j;
                }else{ 
                    j = next[j];
                }
            }
            //KMP算法主体
            int k = 0;
            int l = 0;
            while(k<t.length&&l<p.length){ 
                 if(l==-1||t[k]==p[l]){ 
                      k++;
                      l++;
                 }else{ 
                     l=next[l];
                 }
            }
            //如果长度相等，说明匹配成功
            if(l==p.length){ 
                return k-p.length;
            }else{ 
                return -1;
            }
            
        }
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dvYWlsaXFpMTIxMzQ_size_16_color_FFFFFF_t_70 8]

### 五、代码优化（nextval） ###

#### 思路理解： ####

本质上就是比next更快一步，会更加减少没有必要的回溯。

*  实际上代码的区别只有：  
    next:

while(i<p.length-1){ 
                if(j==-1||p[i]==p[j]){ 
                    i++;
                    j++;
     //这里：next[i] = j;
                }else{ 
                    j = next[j];
                }
            }

nextval:

while(i<p.length-1){ 
                if(j==-1||p[i]==p[j]){ 
                    i++;
                    j++;
                    //这里：
                    if(p[i]!=p[j]){ 
                       nextval[i] = j;
                    }else{ 
                       nextval[i] = nextval[j];
                    }
                }else{ 
                    j = nextval[j];
                }
            }

可以理解为在next的基础上，增加了对下一个位置的提前判断。  
这个的过程有些抽象，但是改动很容易理解，可以直接应用。

*  手写nextval数组思路：（应试）  
    ![\[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-sAsYwQVl-1624693155451)(en-resource://database/652:0)\]][img-sAsYwQVl-1624693155451_en-resource_database_652_0]

#### 代码实现： ####

class Solution { 
        public int strStr(String haystack, String needle) { 
            //字符串转为字符数组
            char[] t = haystack.toCharArray();
            char[] p = needle.toCharArray();
            
            //判空
            if(p.length==0){ 
                return 0;
            }
            //建立nextval数组
            int[] nextval = new int[p.length];
            //要和nextval[0]相同
            int j = -1;
            int i = 0;
            //设置初值为-1
            nextval[0] = -1;
            while(i<p.length-1){ 
                if(j==-1||p[i]==p[j]){ 
                    i++;
                    j++;
                    if(p[i]!=p[j]){ 
                       nextval[i] = j;
                    }else{ 
                       nextval[i] = nextval[j];
                    }
                }else{ 
                    j = nextval[j];
                }
            }
            //KMP算法主体
            int k = 0;
            int l = 0;
            while(k<t.length&&l<p.length){ 
                 if(l==-1||t[k]==p[l]){ 
                      k++;
                      l++;
                 }else{ 
                     l=nextval[l];
                 }
            }
            //如果长度相等，说明匹配成功
            if(l==p.length){ 
                return k-p.length;
            }else{ 
                return -1;
            }
            
        }
    }

![在这里插入图片描述][20210626154943321.png]

### 总结： ###

leetcode算法原题：

> https://leetcode-cn.com/problems/implement-strstr

还可以参考我对这个算法的解析：

> https://blog.csdn.net/woailiqi12134/article/details/118108240

B站视频参考：

> https://www.bilibili.com/video/BV16X4y137qw?from=search&seid=2512319976992657622

> https://www.bilibili.com/video/BV1PD4y1o7nd?from=search&seid=2512319976992657622

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dvYWlsaXFpMTIxMzQ_size_16_color_FFFFFF_t_70]: /images/20221005/f42bb1f2a6094b609f94719093d30840.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dvYWlsaXFpMTIxMzQ_size_16_color_FFFFFF_t_70 1]: /images/20221005/06b534ca9c2c4b67b15cb20544600ff4.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dvYWlsaXFpMTIxMzQ_size_16_color_FFFFFF_t_70 2]: /images/20221005/8ad6ab35d3fc492bafb1ab70fcea3d02.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dvYWlsaXFpMTIxMzQ_size_16_color_FFFFFF_t_70 3]: /images/20221005/831bf557c7174aa29de91024db19a1f6.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dvYWlsaXFpMTIxMzQ_size_16_color_FFFFFF_t_70 4]: /images/20221005/a0b88ac2993b4d38b530a8ba19a5076f.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dvYWlsaXFpMTIxMzQ_size_16_color_FFFFFF_t_70 5]: /images/20221005/004e6fcf78034ced8b340226662d1e16.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dvYWlsaXFpMTIxMzQ_size_16_color_FFFFFF_t_70 6]: /images/20221005/fafc56319ae341c1ad8c73b7c30efea6.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dvYWlsaXFpMTIxMzQ_size_16_color_FFFFFF_t_70 7]: /images/20221005/1d4068b1fdc44303ab1ea61c86a6e840.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dvYWlsaXFpMTIxMzQ_size_16_color_FFFFFF_t_70 8]: /images/20221005/6ed42471e78a4c738db23e5d17d941f0.png
[img-sAsYwQVl-1624693155451_en-resource_database_652_0]: /images/20221005/957ec6ffaa6541fc87b29968d5f11985.png
[20210626154943321.png]: /images/20221005/ae13e299467149f8976cfd2294b61851.png