【算法】字符串查询KMP算法代码实现

题目

找到模式串在主串中的位置，没有返回-1。

原理

不回溯主串，通过计算步长后移子串的方式快速查找字符串，将时间复杂度控制到O(n)。
主要原理是，先在子串中找到所有重复的更小子串，并在重复的后面的子串的最后一位的下标记录子串长度。当与主串匹配出现不一致时，后移失配的前一个下标对应步长，然后继续进行匹配。

代码

public static void main(String[] args) {
    char[] str = "ABCABCAABCABCD".toCharArray();
    char[] pattern = "ABCABCD".toCharArray();
    int[] next = new int[pattern.length];
    getNext(pattern, next);
    System.out.println(Arrays.toString(next));
    int result = searchString(str, pattern, next);
    System.out.println(result);
}

private static int searchString(char[] str, char[] pattern, int[] next) {
    int i = 0;
    int j = 0;
    while (i < str.length && j < pattern.length) {
        if (str[i] == pattern[j]) {
            i++;
            j++;
        } else {
            j = next[j - 1];
        }
    }
    if (j == pattern.length) {
        return i - j;
    }
    return -1;
}

private static void getNext(char[] pattern, int[] next) {
    int i = 1, j = 0; // 分别从模式串的0和1开始寻找重复子串
    while (i < pattern.length) {
        if (pattern[i] == pattern[j]) { // 如果相同
            next[i] = j + 1; // 步长数组中的i对应值设置为j+1
            i++; 
            j++; // 自增i和j
        } else { // 不相同时
            i++; // 自增i
            j = 0; // 重置j
        }
    }
}