字符匹配算法(KMP)

package sunfa.kmp;

/**
 * 朴素字符串匹配算法
 */
public class SimpleKMP {
	public static void main(String[] args) {
		int index = simpleKmp("12444abababab", "444ababab");
		System.out.println(index);
	}

	/**
	 * 朴素字符串匹配算法的一个特点是主字符串指针要回溯
	 * 性能o((n-m+1)m)
	 * @param src
	 * @param dect
	 * @return
	 */
	private static int simpleKmp(String src, String dect) {
		if (dect.length() > src.length())
			return -1;
		char[] srcArr = src.toCharArray();
		char[] dectArr = dect.toCharArray();
		for (int i = 0; i < srcArr.length; i++)
			if ((i + dect.length()) <= srcArr.length
					&& comp(srcArr, dectArr, i, i + dect.length()))
				return i;
		return -1;
	}

	private static boolean comp(char[] srcArr, char[] dectArr, int a0, int a1) {
		int j = 0;
		for (int i = a0; i < a1; i++)
			if (srcArr[i] != dectArr[j++])
				return false;
		return true;
	}
}

package sunfa.kmp;

import java.util.Arrays;

/**
 * 这个算法比较靠谱，而且看的懂 KMP算法分2步：
 * <p>
 * ①根据子字符串得到next数组
 * <p>
 * ②子串与主串进行朴素比较,但是匹配不上的时候就查找next数组。
 * 以前在这个时候是i回溯并且j=0,kmp算法是i不动并且j回溯(根据next数组进行回缩，
 * 找到那个能够匹配上的地方。它怎么知道哪个地方能够匹配的上呢，看看next数组的实现就清楚了。)
 * 
 * next数组的实现：对子串进行迭代，每次取p.substring(0, i)个字符，然后把该字符劈成两半并且比较左半边和右半边是否相等，
 * 如果相等则将两半处的索引n加到next数组中去
 * <p>
 * 
 *
 * /**
 * kmp算法 一种改进的字符串匹配算法，由D.E.Knuth与V.R.Pratt和J.H.Morris同时发现，因此称之为KMP算法。此算法可以在O
 * (n+m
 * )的时间数量级上完成串的模式匹配操作，其基本思想是：每当匹配过程中出现字符串比较不等时，不需回溯指针，而是利用已经得到的“部分匹配”结果将模式向右“
 * 滑动”尽可能远的一段距离，继续进行比较。 参考http://www.iteye.com/topic/501047
 * 
 * KMP算法的思路： 
 * http://iaiai.iteye.com/blog/1140796
 * 
 */
 */
public class KMP {

	String s; // 主字符串
	String p; // 匹配字符串
	int[] next; // 匹配字符串的next数组

	int times; // 记录匹配的次数
	int index; // 记录查找到的位置

	/**
	 * 构造函数，初始化各个成员变量
	 * 
	 * @param s
	 * @param p
	 */
	KMP(String s, String p) {
		this.s = s;
		this.p = p;
		this.next = new int[p.length()];
		for (int i = 0; i < p.length(); i++) {
			if (i == 0) {
				this.next[i] = -1;
			} else if (i == 1) {
				this.next[i] = 0;
			} else {
				// 对某个位置之前的字符串考察其开始部分和结尾部分是否相同
				this.next[i] = next(p.substring(0, i));
			}
		}

		this.times = 0;
		this.index = -1;
	}

	/**
	 * 返回子字符串，开始部分和结尾部分相同的情况下的开始部分的下一个位置，即next值
	 * 
	 * @param p
	 * @return
	 */
	private int next(String p) {
		int length = p.length() / 2;

		while (length > 0) {
			if (p.substring(0, length).compareTo(
					p.substring((p.length() - length), p.length())) == 0) {
				System.out.println(p + "<" + p.substring(0, length) + "="
						+ p.substring((p.length() - length), p.length()));
				return length;
			}
			length--;
		}
		return length;
	}

	/**
	 * 对主字符串进行比较，碰到不匹配，查询next数组；如果新元素和当前不匹配元素相同，则继续next
	 * 
	 * @return
	 */
	boolean match() {
		int i = 0;// 主串索引
		int j = 0;// 子串索引
		int index = -1; // index记录匹配的位置

		while (i < this.s.length() && j < this.p.length()) {
			if (this.s.charAt(i) == this.p.charAt(j)) {// 1、按照朴素模式进行匹配
				if (j == 0) {
					index = i;
				}

				i++;
				j++;
			} else {
				// 一直寻找next，直到和当前元素不相等的元素，将其下标赋值给j
				int newj = this.next[j];// 2、当匹配不上了的时候i不用回溯，只需要根据j的索引去查找next数组
				System.out.print("debug[");
				while ((newj != -1)
						&& (this.p.charAt(newj) == this.p.charAt(j))) {
					// newj回溯
					newj = this.next[newj];

					System.out.print("newj:" + newj + ",i:" + i + ",j:" + j
							+ ",v:" + this.p.charAt(j) + ",next:"
							+ Arrays.toString(next) + ",p:" + p);
				}
				System.out.println("]");

				j = newj;

				if (j == -1) {
					i++;// 主串索引++
					j = 0;// 子串索引重置
				} else {
					index = i - j;
				}
			}
			this.times++;
		}

		if (j == this.p.length()) {
			this.index = index;
			return true;
		} else {
			return false;
		}
	}

	public static void main(String[] args) {
		String s = "1ababcababd1ababcababc_def";
		String p = "ababcababc";
		KMP m = new KMP(s, p);

		// 顺便打印next数组；
		for (int i = 0; i < m.next.length; i++) {
			System.out.print(m.next[i] + ",");
		}
		System.out.println();

		if (m.match()) {
			System.out.println("match");
			System.out.println("match times: " + m.times);
			int index = m.index;
			System.out.println(index);
		} else {
			System.out.println("not match");
		}
	}

}