大白话详解KMP算法

2021-10-28 12:06:54

前后断断续续搞了5个月，每次都以为自己懂了，但是要写的时候都不知从何下手，然后又是各种找博客，看帖子，所以这次试着用自己的语言写一个博客。

首先

首先，KMP算法就是从一个模板字符串（S）中匹配目标字符串（P）。匹配的话，首先就是想到了暴力匹配，也就是用两个下标表示在S的下标（si）和 P的下标（pi), 然后进行循环，如果s.chatAt(si)==p.chatAt(pi)就是si ++， pi++；如果不相等的话，就需要把si = si - pi + 1, pi = 0; ，然后判断 pi == p.length()
相等的话，就是匹配成功，可以返回，不相等就继续。下面贴一下代码，图就不画了。

   public int violenceMatch(String s, String p){
     int sLen = s.length(), pLen = p.length();
     int si = 0, pi = 0;
     while (si < sLen && pi < pLen) {
       if (s.charAt(si) == p.charAt(pi)) {
         si++;
         pi++;
       } else {
         si = si - pi + 1;
         pi = 0;
       }
     }
     if (pi == pLen) {
       return si - pi;
     } else {
       return  -1;
     }
   }

使用暴力匹配的缺点很明显，就是每次匹配（就是s.chatAt(si) != p.chatAt(pi）的时候，需要把 si 的位置置为s.chatAt(si)==p.chatAt(pi)开始的点的下一位，这样会出现很多重复无效的匹配。

KMP算法进行字符串匹配

KMP算法就是把这些重复无效的匹配解决了，具体怎么解决，这个也是KMP算法的精髓（next数组的求解）。关于next数组的求解，我们稍后说，我们先体会一下怎么使用KMP算法来进行字符串匹配（如果只想了解next数组是怎么求出来的，可以跳过这部分），举个例子，有模式串S: "CDABADABCABADABAB", 目标串P: "ABADABAB"用目标串推出的next数组是{0,0,1,0,1,2,3,2}(后面会具体讲怎么推出来的)，现在我们开始使用KMP算法进行匹配。一开始是 si = 0， pi = 0。

我们可以看到这个位置不匹配的，然后因为当前pi == 0 所以直接si += 1 pi 不动进行下一步此时 si = 1，pi = 0

此时也是不匹配的，然后重复上一步，此时 si = 2, pi = 0

当si = 2， pi= 0的时候，s.chatAt(si) == p.chatAt(pi)，所以此时 si += 1, pi += 1，重复这样匹配，我们发现在si = 8,pi=6的时候失配了，这是用就需要用到我们的next数组了。
这里先简单说next数组的一样，是当前下标所对应的最长公共前后缀，注意是最长，不是个数，是长度!!! 公共前后缀，都是基于当前下标来说的。举个例子 ABA 这个next数组是 {0 0 1}对于0下标，没有前后缀，因为只有1个数，对于1的下标，前缀是A，后缀是B，A != B, 所以还是0，对于2的下标，前缀有 A， AB，后缀有 BA，A，所以值为1 ，后面会有详细的介绍，这里只要分辨出前缀和后缀就可以了。

回到正题

我们当前位置是失配，所以需要用到next数组，那么这个next数组在这里有什么用呢？我们试想一下，在当前下标失配，说明我前面的都是可以匹配上的，我们的next数组是保存了最长的公共前后缀，我们是不是可以把失配下标的前一个位置在next数组中对应的最大公共前后缀值来作为目标串（P）移动的距离，因为我当前失配的下标的前一个下标有一定的匹配距离，然后这个下标所对应的前缀是不是可以省略比对，直接移动最长公共前后缀的距离。这里pi = 6的时候失配， next[6 - 1] = 2，也就是前缀AB （下标0、1）和后缀AB（下标4、5），我们是不是可以省略AB的比较，直接从 ABAD的A开始继续匹配。因为对于 pi = 6来说， pi = 4, pi=5都是和S串上可以匹配上，省略pi = 0， pi = 1的比较，直接从pi = 2开始和si= 8 继续比对，所以下标变化是si = 8, pi = next[6 - 1]=2也就是下图：

此时对于si = 8, pi= 2 仍然没有匹配上，然后再次使用next数组， next[2 - 1] = 0，所以有 si = 8, pi = next[2 - 1] = 0

此时还是没有匹配上，但是pi = 0，所以 si+=1，此时 si = 9, pi = 0

后面下去都是匹配上了。所以可以返回下标。
可能看到这里，你还是疑惑这个next下标为什么要这样用呢？这里总结一下，然后就解释next数组的推导过程。我们在失配的时候，就需要移动目标串，问题是移动多少呢？不同于暴力匹配的做法，将 si和pi都一起移动，而是只移动 pi，这个移动的距离，和next数组有关，我们当前失配的位置的前一个位置是可以和S模式串失配前的位置是可以匹配的，所以我们只要移动当前pi的前一个位置的最大公共前后缀距离，然后原本由后缀匹配的字符给前缀匹配（因为知道了最大公共前后缀的距离，所以这部分只是移动而已，不需要再重新的匹配），然后在失配的地方继续进行新的比对。
这里开始讲解一下next的推导。我们在前面提到过，next数组对于当前下标所对应的最长公共前后缀，所以我们从index = 1 开始，因为 0 下标只有1个字符，没有前后缀

对于下标1，我们可以很清楚的看到，前缀是A，后缀是B，A != B, 所以next[index] = 0，对下标index = 2进行查看

对于下标2，我们也可以很清楚的看到，前缀是A、AB，后缀是BA,A，只有A == A，所以next[index] = 1,好像到这里还是很简单，我们可以先推出一个公式，p.chatAt(index) == p.chatAt(next[index - 1]) 成立的话next[index] = next[index - 1] + 1, 不成立的话 next[index] = 0,后面我们就用这个公式进行求解，看下这个公式是否成立，在验证结果之前，我先说一下为什么会得出这样的公式， next数组是保存了最长公共前后缀，这个概念说过很多次了，因为它特别重要。我们对于当前下标，要想找到最长的公共前后缀，最好的办法就是在前一个下标的最长公共前后缀的基础上+1，这点没有问题吧，所以就有了 p.chatAt(index) == p.chatAt(next[index - 1])。那么接下来，我们就来验证一下这个公式的正确性了。对于下标 index = 3，

有p.chatAt(3) != p.chatAt(next[3 - 1])所以next[3] = 0，我们也可以看出next[3]确实是0，继续 index = 4

在index = 4的时候，有 p.chatAt(4) == p.chatAt(next[4 - 1]) 所以next[4] = next[4 - 1] + 1，确实没错，继续index = 5

在next = 5的时候，有p.chatAt(5) == p.chatAt(next[5 - 1]) 所以next[5] = next[5 - 1] + 1,也没有错误，继续 index = 6

在next =6 的时候，有p.chatAt(6) == p.chatAt(next[6 - 1]), 所以next[6] = next[6 - 1] + 1, 也没有错误，继续 index = 7

在next = 7 的时候，有p.chatAt(7) != p.chatAt(next[7 - 1]), 按照公式，此时的next[7] 应该是0 才对呀，但是我写的是 2，我们可以看一下，确实也是2 因为前缀 AB 和后缀AB相等，所以是2，但是这是为什么呢？我们可以知道 p.chatAt(7) 确实是不等于 p.chatAt(next[7 - 1])，但是不要忘记，我们的next保存的是最长公共前后缀，next[7 - 1] = 3，说明下标0 、 1、 2和下标4、5、6是一一对应的，所以我们对下标4 和7进行比较，发现不相等，按照一开始的思路，我们会把next[7]设为0，但是我们可以看一下下标 0、 1、 2 、 3这里，对于下标3 是我们下标7要比较的，但是看一下下标2的位置在next数组是1，这表明了，对于下标2，的最长公共前后缀是1，在求next[3]的时候，我们用p.chatAt(3)和p.chatAt(next[3 - 1])进行比较，对于现在的下标7，我们是不是可以把它当成是下标3 呢？完全可以，因为下标0、1、2和下标4、5、6一一对应，下标3 和7 没有匹配上，就可以把下标7 看成是下标3，此时应该是用 p.chatAt(7) 和 p.chatAt(next[3 - 1]), 对于为什么前面是7 后面是next[3- 1] 而不是next[7 - 1]的，如果用next[7 - 1]了，是不是就陷入了死循环了？其实这里也就是把3的下标当作是7来看待，对于3前面的没有其他影响，所以才是这样的。那么到了此时，我们可以很清晰地求出next数组，然后结合前面的讲解，就是一个完整的KMP了。

总结

第一次写博客写了2000+字，花费了一些心血画图，试图用最简单的话来叙述这个算法，但是好像没有做到，有一些东西在我这个层次还没有看到，所以也没有用到最简单的话来叙述完全部，大家能多看几遍，也是可以理解这个算法的精妙之处。最后贴一下完整代码：

package com.hl.solution;


/**
 * @author Hl
 * @create 2021/3/3 0:18
 */
public class KMP {

    public static void main(String[] args) {
        KMP kmp = new KMP();
        String s = "BBC ABCDAB ABCDABCDABDE";
        String p = "12";
        int i = kmp.kmpMatch(s, p);
        int j = kmp.violenceMatch(s, p);
        System.out.println("KMP算法结果： "+i);
        System.out.println("暴力匹配结果： " + j);

    }
	
  // KMP匹配
    public int kmpMatch(String s, String p){
        int[] next = getNext(p);
        int sLen = s.length(), pLen = p.length();
        int sl = 0, pl = 0;
        while (sl < sLen) {
            if (s.charAt(sl) == p.charAt(pl)) {
                sl++;
                pl++;
            } else if (pl == 0) sl++;
            else pl = next[pl - 1];
            if (pl == pLen) {
                return sl - pl;
            }
        }
        return -1;
    }

  // 求next数组
    public int[] getNext(String p){
        int[] next = new int[p.length()];
        for (int i = 1; i < p.length(); i++) {
            int index = next[i - 1];
            while (index > 0 && p.charAt(i) != p.charAt(index)) {
                index = next[index - 1];
            }
            if (p.charAt(i) == p.charAt(index)) {
                next[i] = index + 1;
            }
        }
        return next;
    }

  // 暴力匹配
    public int violenceMatch(String s, String p){
        int sLen = s.length(), pLen = p.length();
        int si = 0, pi = 0;
        while (si < sLen && pi < pLen) {
            if (s.charAt(si) == p.charAt(pi)) {
                si++;
                pi++;
            } else {
                si = si - pi + 1;
                pi = 0;
            }
        }
        if (pi == pLen) {
            return si - pi;
        } else {
            return  -1;
        }
    }
}

希望大家都能在我这里得到一些收获，感谢看了这么久........

原文链接：https://www.cnblogs.com/hlooog/p/14473958.html

首先

   public int violenceMatch(String s, String p){
     int sLen = s.length(), pLen = p.length();
     int si = 0, pi = 0;
     while (si < sLen && pi < pLen) {
       if (s.charAt(si) == p.charAt(pi)) {
         si++;
         pi++;
       } else {
         si = si - pi + 1;
         pi = 0;
       }
     }
     if (pi == pLen) {
       return si - pi;
     } else {
       return  -1;
     }
   }