KMP Algorithm

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");
	}
}