有关KMP算法

KMP算法：

此算法的本质是首先对于模板字符串进行计算，生成一个数组(next数组)，该数组反映了模板字符串的情况。

例：

S:　　ABADACABABCD

P:　　ABAB

当我们查询到P3与S3(B和D)不相等时，如果是暴力算法，则在从第二个字符开始比较。

而KMP算法则是从P3开始比较(这里的P3只是根据上面举个例子，生成的next数组就是为了找到每一次如果失败后P3的位置，也就是

失配时，模式串向右移动的位数为：失配字符所在位置 - 失配字符对应的next 值)

通过数组再进行查找，以达到降低时间复杂度的目的。

next数组：

{next数组与最大长度值的关系：next 数组相当于“最大长度值” 整体向右移动一位，然后初始值赋为-1。}

本文具体是在理解KMP算法后的回顾，如果要看详解点击下方连接(讲解的十分清楚)：

原文链接：https://blog.csdn.net/v_july_v/article/details/7041827

下面是具体用java实现的例子：

 public class kmp {

     private String ts;

     private String ps;

     kmp(){

     }

     kmp(String ts,String ps){

         this.ts=ts;

         this.ps=ps;

     }

     public void setts(String ts){

         this.ts=ts;

     }

     public void setps(String ps){

         this.ps=ps;

     }

     public int kmpmatch() {                    //KMP开始运算

         int slen=ts.length();

         int plen=ps.length();

         int i=0;

         int j=0;

         int[] next =getNext(ps);

         while(i<slen&&j<plen) {

             if(j==-1||ts.charAt(i)==ps.charAt(j)) {

                 i++;

                 j++;

             }else {

                 j=next[j];

             }

         }

         if(j==plen) {

             return i-j;

         }else {

             return -1;

         }

     }

     public int[] getNext(String ps) {

     char[] p =ps.toCharArray();

     int[] next = new int[p.length];

     next[0]=-1;

     int j=0;

     int k=-1;

     while(j<p.length-1) {                    //此算法的精髓！！！！！

         if(k==-1||p[j]==p[k]) {

             k++;

             j++;

             if(p[j]!=p[k]) {

                 next[j]=k;

             }else {

                 next[j]=next[k];

             }

         }else {

             k=next[k];

         }

     }

         return next;

     }

     public static void main(String[] args) {

         // TODO Auto-generated method stub

         String A = "wdnmwdnmwdnmddnm";

         String B = "wdnmwdnmd";

         kmp k =new kmp();

         k.setts(A);

         k.setps(B);

         System.out.println(k.kmpmatch());        //输出的4

     }

 }

巴特西

有关KMP算法

最新文章

热门文章