最简单的方法理解KMP算法

痛定思痛。 2021-09-20 10:00 375阅读 0赞

# KMP算法 #

>        在求解字符串的匹配问题时，最容易让人想到的便是BF算法，但是由于BF的时间复杂度为O(n\*m)，所以并不是很好。而KMP算法同样用于求解字符串的匹配问题，其时间复杂度为O(n+m)，但是并不是所有人都能理解这种算法，甚至去选择死记硬背。这里并不建议如此做，直接进入正题吧。

>        KMP算法的时间复杂度低的关键便是主串的指针不回溯，只需要更改模式串的指针即可。然而很多人都知道KMP算法的原理，最主要的便是求模式串的next数组，给其一个模式串，可以很快的在纸上求出next数组。但是在面对next数组的代码时，却不能够看懂。终究原因，还是没有完全理解next数组。在这里希望可以用最简单的语言帮助你理解KMP算法。

首先我们假设next\[j\] = k ,那么意味着当指针指向模式串的j时，其真前缀串和真后缀串的长度都为k，所以通过下面的图可以得到 a 串的长度和b串的长度都为k，并且他们的值相匹配。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhbmdfemhhb18_size_16_color_FFFFFF_t_70]  
       那么现在我们要求出next\[j+1\]的值，应该怎么做呢？  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhbmdfemhhb18_size_16_color_FFFFFF_t_70 1]  
       现在我们只需要判断模式串p的p\[k\]和p\[j\]是否相等，如果相等的话，那么是不是便有next\[j+1\] =next\[j\]+1。注意我们已知next\[j\] = k，即next\[j+1\] = k +1,我们将在next的代码中用到。

那么如果不相等呢？那么我们只能在k的前面寻找和j相等的那一个指针。假设next\[k\] = h,那么我们可以得到下图：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhbmdfemhhb18_size_16_color_FFFFFF_t_70 2]  
       那么意味着1区域和2区域（即绿色区域）的字符串相匹配且长度为h，有因为a区域和b区域的字符串相匹配，所以1区域和区域的字符串相匹配，所以我们需要判断p\[h\]和p\[j\]是否相等，如果相等，则有 next\[j+1\] = h + 1，即next\[j+1\]等于next\[k\]+1。如果不相等的话，我们继续递归划分h前面的字符串即可，直到到-1.

接下来便介绍代码吧，如下：

public static int[] getNext(String str){ 
            int[] next = new int[str.length()];
            next[0] = -1; // 因为首字母的前缀串为空串，所以这里规定为-1
            int j = 0;
            int k = -1;
            while(j < next.length-1){ 
                if(k==-1 || str.charAt(j) == str.charAt(k)){ 
                          // k == next[j]
                    ++k; // next[j] + 1
                    ++j;
                    next[j] = k; // next[j+1] = next[j] + 1
                }else{  //不匹配进行递归操作
                    k = next[k];
                }
            }
            return next;
        }

以上便是next的求法，不管p\[k\]和p\[j\]是否匹配，在我们用图推导时结论都是next\[j\]=next\[k\]+1.

在求得next数组后，我们便进行字符串的匹配，同样的假设主串的第i个位置和模式串的第j个位置发生了不匹配，那么可得到下面这张图：

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhbmdfemhhb18_size_16_color_FFFFFF_t_70 3]  
       我们可以知道黄色区域的字符串相互匹配，那么现在我们的目标是在模式串的黄色区域找等于i位置的下标。在我们所求过的next数组，可以知道：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhbmdfemhhb18_size_16_color_FFFFFF_t_70 4]  
       粉色区域为j的前缀子串和后缀子串，对应主串中的如下区域：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhbmdfemhhb18_size_16_color_FFFFFF_t_70 5]  
       我们可以知道粉色区域相互匹配，那么现在我们只需要判断i和k的字符是否相匹配，如果匹配的话，j = next\[j\]。如果不匹配的话，我们继续递归下去即可，类似于递归求next数组。  
       不知道你有没有这样的疑问，为什么要在k位置判断是否相等，k+1不可以吗？答案是不可以的，如果以k+1为例，那么则认为k的字符包含在粉色区域。如果包含进去的话，next\[j\]又是一个新的k，有陷入了刚才的问题。

public static int KMP(String str,String pattern){ 
            int[] next = getNext(str);
            int strLen = str.length()-pattern.length();
            int i = 0;
            int j = 0;
            while(i <= strLen && j < pattern.length()){ 
                if(j == -1 || str.charAt(i) == pattern.charAt(j)){ 
                	// j == -1,即说明模式串的首字符和主串的i都不匹配
                    i++;
                    j++;
                }else{ 
                    j = next[j];
                }
                if(j == pattern.length()){ 
                    break;
                }
            }
            return i-j;
        }

接下来我们进行KMP的优化算法，优化算法同样是为了求解next数组，但为什么要求解next数组呢？  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhbmdfemhhb18_size_16_color_FFFFFF_t_70 6]  
        假设p\[k\] == p\[j\]，那么是不是意味着i位置的字符和k位置的字符不相等呢，所以此时我们直需要判断next\[k\]位置的字符和i是否匹配，可以跳过一些没必要判断的字符。而next\[k\] = next\[j\],即 i 是否和next\[next\[j\]\]相匹配。

public static int[] getNext2(String str){ 
            int[] next = new int[str.length()];
            next[0] = -1;
            int j = 0;
            int k = -1;
            while(j < next.length-1){ 
                if(k==-1 || str.charAt(j) == str.charAt(k)){ 
                    ++k;
                    ++j;
                    if(str.charAt(j) == str.charAt(k))
                        next[j] = next[k]; 
                    else
                        next[j] = k;
                }else{ 
                    k = next[k];
                }
            }
            return next;
        }

以上便是KMP算法的求解了，面对一堆的关系，建议以画图的方式来表示出来，更加直观，容易理解。  
       个人博客：[https://wshuaigit.github.io/][https_wshuaigit.github.io]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhbmdfemhhb18_size_16_color_FFFFFF_t_70]: /images/20210812/9306e152f1fa440d80ba85ad9939e559.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhbmdfemhhb18_size_16_color_FFFFFF_t_70 1]: /images/20210812/cbc3779ed8b348a7b029ae1319396a1f.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhbmdfemhhb18_size_16_color_FFFFFF_t_70 2]: /images/20210812/0a01059859634b4ea0f132c9707459e8.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhbmdfemhhb18_size_16_color_FFFFFF_t_70 3]: /images/20210812/d9713c059c2246b5bb53c92f8480f51c.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhbmdfemhhb18_size_16_color_FFFFFF_t_70 4]: /images/20210812/099e1d39994f43fa971f1bb97dccde58.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhbmdfemhhb18_size_16_color_FFFFFF_t_70 5]: /images/20210812/2322b797573c4c29b71dfb4ead1b4371.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhbmdfemhhb18_size_16_color_FFFFFF_t_70 6]: /images/20210812/58c66680e1c04457aca3fe730ffc6f39.png
[https_wshuaigit.github.io]: https://wshuaigit.github.io/