KMP算法（Java实现）

      KMP算法同BF算法一样，也是字符串匹配算法，BF算法是主串指针与子串指针一一进行比较，如果失配，那么主串和子串的指针都需要进行回退，而KMP的算法思想是主串指针不回退，子串的指针只需要回退到一定的位置也可以完成字符串的匹配，学习一下吧

KMP算法的原理

这里我只是为了解析KMP的代码，原理问题就不花时间分析了
直接来看大话数据结构里面的讲解：

通过上面的叙述知道主串指针不回退，子串指针回退到一定的位置，这个位置是通过next数组来确定的，而next数组只与子串有关

next数组的求法

通过阅读上面的步骤，自己已经可以求next数组了，但是如何抽象成为Java代码，首先需要掌握几条规律，举一组例子：

1. 我这里的代码实现中next值都比大话数据结构中少1，从-1开始，其实是一样的，我这样写的原因是在子串回退的时候直接回退next个位置，而不用回退next+1，原理 是不变的
2. next[0] = -1,next[1] = 0
3. 如果next值要增加，那么是逐一递增的，每次只加1，所以next的位置和前一个位置的next值有很大关系
4. 如果要进行比较，必须定义一个指针，用来记录已经匹配好子串的长度，如果该匹配成功，则在匹配好的长度基础上加1记录为当前位置的next值
5. 如果当前匹配失败，k要进行回退，不用一个一个回退，而是直接回退至该位置的next值处，这是一个规律。

知道了这些规律后，一起看一下代码实现：

    /**
     * 计算next数组
     * @param sub 子串
     * @return 返回计算好的next数组
     */
    public static int[] getNext(String sub) {
        int[] next = new int[sub.length()];

        next[0] = -1;
        if(sub.length() >= 2) {
            next[1] = 0;
        } else {
        	return next;
        }

        //定义指针k，来与j-1进行比较
        int k = 0;
        int j = 2;
        while(j < sub.length()) {
            //如果k==-1，就需要重头开始比较，给该位置的next赋值为k+1=0，j++求下一个元素的next值，k++从0开始重新比较
            //如果k！=-1，则该次比较的这个字母和k相同，只需要在前一个匹配到的next上加1，注意是匹配上的
            if(k==-1 || sub.charAt(k) == sub.charAt(j-1)) {
                next[j] = k+1;
                j++;
                k++;
            } else {
                //如果匹配不上，那么k进行回退，回退是有规律的，直接回退到next[k]位置
                k = next[k];
            }
        }
        return next;
    }

写好了 next 数组，然后写调用函数，这里其实可以套用BF算法的模板 ，需要注意主串指针不回退，子串指针回退的位置从next数组中对应位置取即可。

/**
     *
     * @param str 主串
     * @param sub 子串
     * @param pos 开始位置
     * @return 匹配位置
     */
    private static int kmp(String str, String sub, int pos) {
        //pos的合法性判断
        if(pos >= str.length() || pos < 0 || sub.length()==0) {
            return -1;
        }
        //分别为主串和子串定义指针
        int i = pos;
        int j = 0;
        //拿到已经计算好的next数组
        int[] next = getNext(sub);
        while (i < str.length() && j < sub.length()) {
            //j==-1的意思是：当第一个元素都没有匹配上，那么j会回退到-1，这时主串的指针应该往前走一个，子串从-1走到0，重新开始匹配
            //其余j！=-1的情况，就判断主串指针与子串指针是否相同，相同同时加，不相同则主串不动，子串回退
            if(j == -1 || str.charAt(i) == sub.charAt(j)) {
                i++;
                j++;
                continue;
            }
            //i不回退，j直接从next拿到对应的位置进行回退
            j = next[j];
        }
        if(j >= sub.length()) {
            return i-j;
        }
        return -1;
    }

KMP的优化

根据上面的描述，直接抽象出代码：

    /**
     * 返回nextval数组
     * @param sub 子串
     * @return 返回nextval数组
     */
    public static int[] getNextVal(String sub) {
        //先拿到next数组
        int[] next = getNext(sub);
        //创建nextVal数组
        int[] nextVal = new int[next.length];
        for (int i = 0; i < next.length; i++) {
            //定义两个指针
            int iNext = i;
            int index = next[iNext];
            while (index >= 0) {
                //如果相等，两个指针根据next值进行回退，如果不相等，直接退出
                if(sub.charAt(index) == sub.charAt(iNext)) {
                    iNext = index;
                    index = next[index];
                } else {
                    break;
                }
            }
            nextVal[i] = index;
        }
        return nextVal;
    }

其实，也可以在计算next数组的过程中直接进行优化：

从开始赋值时，就对nextVal赋值为优化后的值，再后面迭代时，只需要每一步赋值时进行判断即可。

    private static int[] getNextval(String sub) {
        int[] nextval = new int[sub.length()];
        nextval[0] = -1;
        if(sub.length() >= 2) {
            nextval[1] = 0;
        } else {
        	return nextval;
        }

        //定义指针k，来与j-1进行比较
        int k = 0;
        int j = 2;
        while(j < sub.length()) {
			//如果k==-1，就需要重头开始比较，给该位置的next赋值为k+1=0，j++求下一个元素的next值，k++从0开始重新比较
            //如果k！=-1，则该次比较的这个字母和k相同，只需要在前一个匹配到的next上加1，注意是匹配上的
            if(k == -1 || sub.charAt(k) == sub.charAt(j-1)) {
                j++;
                k++;
                //每次赋值前都要进行判断，保证赋值过的数组都是优化过的
                if(sub.charAt(k) != sub.charAt(j-1)) {
                    nextval[j-1] = k;
                }else {
                    nextval[j-1] = nextval[k];
                }
            }else {  
            	//如果匹配不上，那么k进行回退，回退是有规律的，直接回退到next[k]位置
                k = nextval[k];
            }
        }
        return nextval;
    }