KMP算法浅析

具体参见: KMP算法详解

背景

KMP算法之所以叫做KMP算法是因为这个算法是由三个人共同提出来的,就取三个人名字的首字母作为该算法的名字。其实KMP算法与BF算法的区别就在于KMP算法巧妙的消除了指针i的回溯问题,只需确定下次匹配j的位置即可,使得问题的复杂度由O(mn)下降到O(m+n)

KMP算法的思想就是:在匹配过程称,若发生不匹配的情况,如果next[j]>=0,则目标串的指针i不变,将模式串的指针j移动到next[j]的位置继续进行匹配;若next[j]=-1,则将i右移1位,并将j置0,继续进行比较。   在KMP算法中,为了确定在匹配不成功时,下次匹配时j的位置,引入了next[]数组,next[j]的值表示P[0...j-1]中最长后缀的长度等于相同字符序列的前缀。 对于next[]数组的定义如下:   1) next[j]=-1  j=0   2) next[j]=max k:0<k<j P[0...k-1]=P[j-k,j-1]   3) next[j]=0  其他 如:   P      a    b   a    b   a   j       0   1    2   3   4   next -1  0    0   1   2 即next[j]=k>0时,表示P[0...k-1]=P[j-k,j-1]

next的求解程序如下:

 1 private int[] next(String str){
 2         if(str == null || str.length() == 0){
 3             return null ;
 4         }
 5         int [] next = new int [str.length()] ;
 6         next[0] = -1 ;
 7         int lastSame = 0 ;
 8         for(int i = 1 ; i < str.length() ; i++ ){
 9             char temp = str.charAt(i) ;
10             next[i] = lastSame ;
11             if(temp == str.charAt(lastSame)){                
12                 lastSame++ ;
13             }else{
14                 lastSame = 0 ;
15             }            
16         }
17         
18         return next ;
19     }

通过next采用KMP算法判断是否匹配的代码如下:

 1 /**
 2      * 若src包含dest子串,则返回src中dest子串出现的位置(首字符的位置),
 3      * 若不包含,则返回-1
 4      * @param src
 5      * @param dest
 6      * @return
 7      */
 8     private int KMPmatch(String src, String dest){
 9         if(src == null || dest == null || src.length() < dest.length()){
10             return -1 ;
11         }
12         int [] next = next(dest);
13         int i = 0 ; 
14         int j = 0 ;
15         while(i < src.length()){
16             if((j == -1) || (src.charAt(i) == dest.charAt(j))){
17                 i++ ;
18                 j++ ;
19             }else{
20                 j = next[j] ;
21             }
22             
23             if(j == (dest.length())){
24                 return i-j ;
25             }
26         }
27         
28         return -1 ;
29     }

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • No.002 Add Two Numbers

    Add Two Numbers Total Accepted: 160702 Total Submissions: 664770 Difficulty: Med...

    mukekeheart
  • Java基础--JDK的安装和配置弄懂 JRE、JDK、JVM 之间的区别与联系

      Java是一门面向对象的编程语言,不仅吸收了C++语言的各种优点,还摒弃了C++里难以理解的多继承、指针等概念,因此Java语言具有功能强大和简单易用两个特...

    mukekeheart
  • Java基础——集合框架

      Java的集合框架是Java中很重要的一环,Java平台提供了一个全新的集合框架。“集合框架”主要由一组用来操作对象的接口组成。不同接口描述一组不同数据类型...

    mukekeheart
  • KMP算法学习(详解)

    kmp算法又称“看毛片”算法,是一个效率非常高的字符串匹配算法。不过由于其难以理解,所以在很长的一段时间内一直没有搞懂。虽然网上有很多资料,但是鲜见好的博客能简...

    Angel_Kitty
  • leetcode: 206. Reverse Linked List

    JNingWei
  • 数据结构 | 每日一练(28)

    ——老子

    C语言入门到精通
  • 模式匹配KMP算法

    匹配到j=5时失效了,BF算法里我们会使i=1,j=0,再看s的第i位开始能不能匹配,而KMP算法接下来就去比较T[2](next[5]=2)和S[5]

    饶文津
  • c/c++补完计划(七): 哨兵节点

    sean_yang
  • leetcode:83 删除排序链表中的重复元素

    问题? 如果next没有值的话,会报错的。 因为要相等啊,比较啊,有值才能比较是吧。 那为什么p.next=p.next.next;如果p.next.ne...

    用户7873631
  • 吃透洋葱模型

    作者:掘金@苏里 https://juejin.im/post/6844904025767280648

    zz_jesse

扫码关注云+社区

领取腾讯云代金券