本文共 2771 字，大约阅读时间需要 9 分钟。
package com.tobaidu.algorithm.kmp;public class KMP { static int[] P; /** * 对子串加以预处理，从而找到匹配失败时子串回退的位置 * * @param B * ，待查找子串的char数组 * @return */ public static int[] preProcess(char[] B) { int size = B.length; int[] P = new int[size]; P[0] = 0; int j = 0; for (int i = 1; i < size; i++) { while (j > 0 && B[j] != B[i]) { j = P[j]; } if (B[j] == B[i]) { j++; } P[i] = j; } return P; } /** * KMP实现 * * @param parStr * @param subStr * @return */ public static void kmp(String parStr, String subStr) { int subSize = subStr.length(); int parSize = parStr.length(); char[] B = subStr.toCharArray(); char[] A = parStr.toCharArray(); int j = 0; int k = 0; for (int i = 0; i < parSize; i++) { while (j > 0 && B[j] != A[i]) { j = P[j - 1]; } if (B[j] == A[i]) { j++; } if (j == subSize) { j = P[j - 1]; k++; } } } public static void main(String[] args) { // 回退位置数组为P[0, 0, 0, 0, 0, 0] kmp("abcdeg, abcdeh, abcdef!这个会匹配1次", "abcdef"); // 回退位置数组为P[0, 0, 1, 2, 3, 4] kmp("Test ititi ititit! Test ititit!这个会匹配2次", "ititit"); }}
package com.tobaidu.algorithm.kmp;public class SubStrFind { /** * 字符串查找（枚举方法） * * @param parStr * @param subStr * @return */ public static void strFind(String parStr, String subStr) { int parSize = parStr.length(); int subSize = subStr.length(); char[] B = subStr.toCharArray(); char[] A = parStr.toCharArray(); boolean flag = true; int times = 0; int j = 0; int k = 0;// k记录父串匹配正确的位置或者匹配不正确的回退位置 // i记录父串的当前比较字符的位置 for (int i = 0; i < parSize; i++) { if (B[j] == A[i]) { j++; // 第一次时记录父串回退位置 if (flag) { k = i; flag = false; } } else { // 不匹配时回退位置重置，比较继续进行 i = ++k; j = 0; flag = true; } if (j == subSize) { j = 0;// 匹配时只需把子串回退位置重置，比较继续进行 flag = true; times++; } } }}
package com.tobaidu.algorithm.kmp;public class TimeConsumer { private static int times = 1000000; public static void test(String parStr, String subStr) { long start = 0; long end = 0; System.out.println("父串: " + parStr); System.out.println("子串: " + subStr); start = System.currentTimeMillis(); KMP.P = KMP.preProcess(subStr.toCharArray()); for (int i = 0; i < times; i++) { KMP.kmp(parStr, subStr); } end = System.currentTimeMillis(); System.out.println("Time for KMP: " + (end - start)); start = System.currentTimeMillis(); for (int i = 0; i < times; i++) { SubStrFind.strFind(parStr, subStr); } end = System.currentTimeMillis(); System.out.println("Time for Enumeration: " + (end - start)); System.out.println("-------------------------------------"); } public static void main(String[] args) { test("abcdeg, abcdeh, abcdef!这个会匹配1次", "abcdef"); test("Test ititi ititititd! Test ititititd!这个会匹配2次", "ititititd"); }}
转载地址：http://hswob.baihongyu.com/