VB.net 2010 视频教程 VB.net 2010 视频教程 python基础视频教程
SQL Server 2008 视频教程 c#入门经典教程 Visual Basic从门到精通视频教程
当前位置:
首页 > 编程开发 > Java教程 >
  • 解读KMP算法

前后断断续续搞了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算法的精髓(next数组的求解)。 关于next数组的求解,我们稍后说,我们先体会一下 怎么使用KMP算法来进行字符串匹配(如果只想了解next数组是怎么求出来的,可以跳过这部分), 举个例子,有模式串S: "CDABADABCABADABAB", 目标串P: "ABADABAB"用目标串推出的next数组是{0,0,1,0,1,2,3,2}(后面会具体讲怎么推出来的),现在我们开始使用KMP算法进行匹配。一开始是 si = 0, pi = 0
alt kmp
我们可以看到这个位置不匹配的,然后因为当前pi == 0 所以直接si += 1 pi 不动 进行下一步 此时 si = 1,pi = 0
alt kmp

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

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也就是下图:
alt kmp

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

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

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

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

对于下标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,
alt next

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

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

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

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

在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


相关教程