KMP算法动态演示

KMP算法

1.动态演示

https://tsccg-oss.oss-cn-guangzhou.aliyuncs.com/image/KMP%E7%AE%97%E6%B3%95%E5%8A%A8%E6%80%81%E6%BC%94%E7%A4%BA.gif

2.代码实现

    @Testpublic void test5(){String parent = "ABC ABCDAB ABCDABCDABDE";String child  = "ABCDABD";List<Integer> result = kmpSearch(parent, child);System.out.println(result);}// 生成部分匹配表（前缀函数）private static int[] computeLPSArray(String pattern) {int[] next = new int[pattern.length()];int length = 0; // 记录前一个最长前缀后缀的长度int i = 1;// 第一个字符的部分匹配值为0next[0] = 0; // 计算next数组while (i < pattern.length()) {char a = pattern.charAt(i);char b = pattern.charAt(length);if (a == b) {length++;next[i] = length;i++;} else {if (length != 0) {length = next[length - 1]; // 回退到上一个长度} else {next[i] = 0;i++;}}}return next;}// KMP搜索算法public static List<Integer> kmpSearch(String parentStr, String childStr) {List<Integer> result = new ArrayList<>();int parentStrLen = parentStr.length();int childStrLen = childStr.length();// 创建next数组，用于存储模式串的部分匹配值int[] next = computeLPSArray(childStr);int i = 0; // text的索引int j = 0; // pattern的索引while (i < parentStrLen) {char a = parentStr.charAt(i);char b = childStr.charAt(j);if (a == b) {i++;j++;}if (j == childStrLen) {// 找到匹配，返回起始索引result.add(i - j);j = next[j - 1]; // 继续寻找下一个匹配} else if (i < parentStrLen && childStr.charAt(j) != parentStr.charAt(i)) {// 不匹配时if (j != 0) {j = next[j - 1];} else {i++;}}}return result;}