KMP算法和next数组详解

KMP算法和next数组详解

KMP算法主要是用来求解子串在主串中第一次出现的位置，并返回这个子串的位置的一种提高效率的方法。在讲解KMP算法之前，我们先来看看求子串在主串中位置的一般解法，即暴力解法。

 

1.暴力解法

 public static int BF(String str,String sub){
        if(str == null || sub == null){
            return -1;
        }
        int lenStr = str.length();
        int lenSub = sub.length();
        if(lenStr == 0 ||  lenSub == 0){
            return -1;
        }
        int i = 0;
        int j = 0;
        while (i < lenStr && j < lenSub ){
            if(str.charAt(i) == sub.charAt(j)){
                i++;
                j++;
            }else {
                i = i - j + 1;
                j = 0;
            }
        }
        if(j >= lenSub){
            return i-j;
        }
        return -1;
    }
    public static void main(String[] args) {
        System.out.println(BF("ababcabcdabcde","abcd"));
        System.out.println(BF("ababcabcdabcde","abcf"));
        System.out.println(BF("ababcabcdabcde","ab"));
    }

 2.KMP算法

        KMP算法和暴力解法的区别就是,在暴力解法主串中如果i和子串j中不匹配，则i返回到开始匹配的地方并+1，但KMP中不用返回，继续保持在原位。在子串中的j会返回到一个“特殊”位置，而这个特殊位置就是我们接下来要讲的。

首先我们看看什么叫next数组：

2.1next数组的含义：

 2.2next数组练习

(1).  k值的求法：找到匹配成功部分的两个相等的真子串(不包含本身），一个以下标0开始，一个以下标j-1结尾。

(2).  不管什么时候next[0]都=-1，next[1]=0.

2.2.1例题1

 例题2：

 2.3求解数组next[i+1]的值

         我们通过上面自己的计算可以求得next[i+1]数组得值，但是我们用程序就需要一个函数来解决，下面我们来求其函数：

 推导过程：从上图之第一次k退回到p[3]的位置，假设p[i] == p[k]

 那如果p[i] != p[k]时：next[i+1]=什么呢？

3.java来实现代码 第一步：进入遍历主串和子串的条件

//首先我们先来列出条件
 public static int KMP(String str,String sub,int pos){
        if(str == null || sub ==null){
            return -1;
        }
        int lenStr = str.length();
        int lenSub = sub.length();
        if(lenStr == 0 || lenSub == 0){
            return  -1;
        }
         if(pos < 0 || pos >= lenStr){
            return -1;
        }

第二步：进行主串和子串的遍历

 int i = pos;//遍历主串
         int j = 0;//遍历子串
         while (i < lenStr && j < lenSub){
             //j==-1表示一开始就匹配失败
             if(j==-1 || str.charAt(i) == sub.charAt(j)){
                 i++;
                 j++;
             }else {
                 j = next[j];
             }
         }
         if(j >= lenSub){
          return i-j;
      }
         return -1;
    }

第三步：写出next数组，来保存子串j回退的位置

int [] next = new int[lenSub];
getNext(sub,next);//求得j回退得位置
 public static void getNext(String sub,int[] next){
        next[0] = -1;//开始的next[0]默认是-1
        next[1] = 0;//默认next[1]是0
        int i = 2;//默认i从第三个位置开始
        int k = 0;
        for (; i < sub.length();i++) {
            //p[i-1] == p[k];
            //这里是sub.charAt(i - 1)是因为之前i是从第三个位置开始的，要用i的前一项
             if (k==-1 || sub.charAt(i - 1) == sub.charAt(k)) {
                   next[i] = k+1;//之前计算得都是next[i+1]=k+1,这里是因为i是第三个位置开始 
                                  //得，因此是next[i]=k+1;
                   k++;
                   i++;
            }else{
                 k = next[k];//如果第一次退回的k和之前的sub.charAt(i-1)不同，则继续往下退
            }
        }
    }

4.next的简化数组nextval数组