Java数据结构之KMP算法详解以及代码实现

public static int bf(String word, String k) {
    char[] wordChars = word.toCharArray();
    char[] keyChars = k.toCharArray();
    for (int i = 0; i < wordChars.length; i++) {
        int j = 0, x = i;
        //依次匹配
        while (x < wordChars.length && j < keyChars.length && wordChars[x] == keyChars[j]) {
            x++;
            j++;
        }
        if (j == keyChars.length) {
            return i;
        }
    }
    return -1;
}

public static int[] getNext(String word) {
    int[] next = new int[word.length()];
    //从两个字符的子串开始遍历
    for (int i = 1; i < word.length(); i++) {
        int k = i;
        //从最大的最长匹配值开始缩短
        while (k > 0) {
            //如果前缀等于后缀，那么表示获取到了最长匹配，直接返回
            if (word.substring(0, k).equals(word.substring(i - (k - 1), i + 1))) {
                next[i] = k;
                break;
            }
            k--;
        }
    }
    return next;
}

public static int[] getNext2(String k) {
    int[] next = new int[k.length()];
    char[] chars = k.toCharArray();
    //i表示匹配的字符索引，pre表示前一个子串的最长匹配长度，即next[i-1]
    int i = 1, pre = next[i - 1];
    while (i < k.length()) {
        //如果新增的字符与前一个子串的最长匹配子串前缀的后一个字符相等
        if (chars[i] == chars[pre]) {
            //next[i]=next[i-1]+1
            pre++;
            next[i] = pre;
            //继续后移
            i++;
        }
        //如果不相等，且前一个子串的最长匹配长度不为0
        //那么求i-1的最长匹配长度子串的最长匹配长度子串，即pre=next[next[i-1]-1]
        //然后在下一轮循环中继续比较chars[i] == chars[pre]，此时i并没有自增
        else if (pre != 0) {
            //next[next[i-1]-1]
            pre = next[pre - 1];
        }
        //如果不相等，且前一个子串的最长匹配长度为0，那么说明当前子串的最长匹配长度也为0
        else {
            //当前子串的最长匹配长度为0
            next[i] = 0;
            //继续后移
            i++;
        }
    }
    return next;

public static int kmp(String word, String k) {
    int[] next = getNext(k);
    //i,j分别表示主串和子串的匹配进度
    int m = word.length(), n = k.length(), i = 0, j = 0;
    //如果i匹配完毕，那么退出循环
    while (i < m) {
        //如果字符相等，那么向后推进i、j
        if (word.charAt(i) == k.charAt(j)) {
            i++;
            j++;
            //如果匹配到了一个完整的子串
            if (j == n) {
                //返回起始索引
                return i - n;
            }
        }
        //如果当前子串进度为0，那么子串不需要回退，主串向后推进i
        else if (j == 0) {
            i++;
        }
        //如果当前子串进度不为0，那么子串需要回退，主串不需要向后推进i
        else {
            //子串进度j回退
            j = next[j - 1];
        }
    }
    return -1;
}

public static List<Integer> kmpAll(String word, String k) {
    List<Integer> res = new ArrayList<>();
    int[] next = getNext(k);
    //i,j分别表示主串和子串的匹配进度
    int m = word.length(), n = k.length(), i = 0, j = 0;
    //如果i匹配完毕，或者j匹配完毕，那么退出循环
    while (i < m) {
        //如果字符相等，那么向后推进i、j
        if (word.charAt(i) == k.charAt(j)) {
            i++;
            j++;
            //如果匹配到了一个完整的子串
            if (j == n) {
                //将起始索引加入结果集
                res.add(i - n);
                //子串进度j回退
                j = next[j - 1];
            }
        }
        //如果当前子串进度为0，那么子串不需要回退，主串向后推进i
        else if (j == 0) {
            i++;
        }
        //如果当前子串进度不为0，那么子串需要回退，主串不需要向后推进i
        else {
            //子串进度j回退
            j = next[j - 1];
        }
    }
    return res;
}