Kmp算法（java）_kmp算法 java

kmp算法用于解决字符串匹配的问题，典型例题力扣28.实现Strstr() 28. 实现 strStr() - 力扣（LeetCode） (leetcode-cn.com)

kmp算法的核心：在当前对字符串和子字符串检索的过程中，若出现了不匹配，充分利用已经匹配的部分

具体如何理解可以看字符串匹配的KMP算法 - 阮一峰的网络日志 (ruanyifeng.com)

kmp算法分为两个部分

①创建字符串的next数组

②在暴力算法的基础上通过next数组回溯 j 来减少时间复杂度

java代码实现

    public static int Kmp(String str1, String str2, int[] next) {  
        for(int i = 0, j = 0; i < str1.length(); i++) {
            while(j > 0 && str1.charAt(i) != str2.charAt(j)) {  //不匹配的情况下
                j = next[j -1];  //通过next数组回溯j
            }
            if(str1.charAt(i) == str2.charAt(j)) {  //匹配的情况下
                j++;
            }
            if(j == str2.length()) {   //匹配成功返回
                return i - j +1;
            }
        }
        return -1;  //匹配不成功返回-1
    }

Next数组

next数组作用：创建个与子字符串位数相同的数组，每个位置上储存截至当前位置前后缀最长共有元素长度。（"前缀"指除了最后一个字符以外，一个字符串的全部头部组合；"后缀"指除了第一个字符以外，一个字符串的全部尾部组合。）

next数组有3种写法，

如字符串"ABCDABD"

写法1：0000120 表示截至当前位置的最长相等前后缀 （个人感觉代码实现最好理解的方法，本文用的此方法）

写法2:-1000012 在写法1基础上右移，第一位改为-1

写法3：0111123 第一位为0，其他看截至前一位的最长相等前后缀+1，（一般的数据结构教材用的是此方法，考试手写也大多是次方法，但个人感觉在代码实现上并不好用）

创建Next数组代码实现（java）

①初始化next数组

②前后缀不相同的情况：j重复回退j=next[j-1]，直到j==0或前后缀相同

③前后缀相同情况：j++

④给next数组赋值next[i]=j

public static int[] CreatNext(String str) {
        int[] next = new int[str.length()];
        next[0] = 0;
        for(int i = 1, j = 0; i < str.length(); i++) {
            while(j > 0 && str.charAt(i) != str.charAt(j)) {
                j = next[j - 1];
            }
            if(str.charAt(i) == str.charAt(j)) {
                j++;
            }
            next[i] = j;
        }
        return next;
    }