搜 索

使用Java语言实现KMP算法

  • 1.1k阅读
  • 2021年01月12日
  • 0评论

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;

    }
}
评论区
暂无评论
avatar