KMP 算法确实不太容易理解,即使我能用PPT模拟出来指针的操作,但对其中核心的 Next 数组的代码实现还是有些困惑。
我再详细学习一下Next数组的实现再补充该文章。抱歉!

耗尽了我好多脑细胞 - -!

如果对 KMP 中的核心 Next 数组实现有兴趣,可以参考这些优质课程:

数据结构与算法基础--第06周05--第4章串、数组和广义表5-4.3串的操作--串的匹配算法2--KMP算法
懒猫老师-数据结构-(15)KMP算法2-next数组(模式匹配,字符串匹配)
KMP字符串匹配算法2

package KMP;

import java.util.Arrays;

public class KMPAlgorithm {
    public static void main(String[] args) {
        String str = "BBC ABCDAB ABCDABDDABDE";
        String subString = "ABCDABD";
        int[] next = getNext(subString);
        System.out.println("next = " + Arrays.toString(next));
        int index = Index_KMP(str, subString, next);
        System.out.println("索引值为: " + index);

    }

    /**
     * KMP搜索算法
     * 
     * @param str1 要查找的主串
     * @param str2 子串
     * @param next 部分匹配表
     * @return 如果是-1,则没有匹配到,否则返回到第一个匹配的位置
     */
    public static int Index_KMP(String str1, String str2, int[] next) {
        // 初始化指针位置
        int i = 0;
        int j = 0;
        // 开始循环比较
        while (i < str1.length() && j < str2.length()) {
            if (j == -1 || str1.charAt(i) == str2.charAt(j)) {
                ++i;
                ++j;
                // 继续比较后序字符
            } else {
                j = next[j]; // 模式串向后移动
            }
        }
        if (j >= str2.length()) { // 因为下标是从0开始的
            return i - str2.length();
        } else {
            return -1; // 未找到
        }
    }

    /**
     * 获取字符串的部分匹配值
     * 
     * @param dest
     * @return
     */
    public static int[] getNext(String dest) {
        // 创建一个Next数组,保存部分匹配值
        int i = 0; // 前指针
        int j = -1;// 后指针
        // 创建next数组保存部分匹配值
        int[] next = new int[dest.length()];
        next[0] = -1;
        while (i < dest.length() - 1) {
            if (j == -1 || dest.charAt(j) == dest.charAt(i)) {
                i++;
                j++;
                next[i] = j;
            } else {
                j = next[j];
            }
        }
        return next;

    }
}
Last modification:January 12th, 2021 at 12:33 am
如果觉得我的文章对你有用,请随意赞赏