KMP算法

什么是KMP？

KMP算法要解决的问题就是在字符串（也叫主串）中的模式（模式串）定位问题。说简单点就是我们平时常说的关键字搜索。

 传统的关键字搜索算法当模式串当前字符与主串当前匹配字符不等时，主串指针需要回溯至开始比较的首位的下一位，模式串指针归零。

KMP算法就是解决了主串指针回溯的问题。

public class KMP {

    public static int KMP(String str1, String str2) {
        int len1 = str1.length(); // str1的长度 主串
        int len2 = str2.length();// str2的长度 模式串
        char[] arr1 = str1.toCharArray(); // 字符串转成字符数组
        char[] arr2 = str2.toCharArray();
        int[] next = new int[len2]; // next 存放 str[i]!= sre2[j]时 j的下个位置
        next = next(arr2);
        int i = 0; // 主串指针
        int j = 0;// 模式串指针
        while (j < len2 && i < len1) {

            if (j == -1 || arr1[i] == arr2[j]) {
                i++;
                j++;
            } else {
                j = next[j];
            }
        }

        if (j == len2) {// 主串含有模式串返回主串中模式串第一个字符的位置
            return i - j;
        } else {// 不含有返回-1
            return -1;
        }
    }

    public static int[] next(char[] arr) { // 当主串str1[i]!= 模式串 str2[j] 时 j
                                            // 应指向的位置 next[j]
        int len = arr.length;
        int next[] = new int[len];
        next[0] = -1;
        int k = -1;
        int j = 0;
        while (j < len - 1) {
            if (k == -1 || arr[j] == arr[k]) {
                next[++j] = ++k;
            } else {
                k = next[k];
            }
        }
        return next;
    }

    public static void main(String[] args) {
        String str1 = "jiaorenzhan";
        String str2 = "ren";
        int index = KMP(str1, str2);
        System.out.println(index);
    }
}