KMP字符串匹配算法

KMP算法的Java实现：

1. KMP算法的思路：
1) 首先对模式串构建next数组，表示当某一位不匹配的时候需要回溯的下一个位置；
2) 然后在对主串使用该模式串进行匹配，当遇到不相等的地方，查询next数组，选择模式串中下一个要匹配的位置的字符；
如果该字符和当前不匹配的字符一样的话，则进一步获取新位置在next数组的值，直到要匹配位置的字符是新的字符；
(不要此步骤也可以，此步骤更加优化)
3) 直到到达模式串结尾。

KMP算法的复杂度：

首先生成匹配字符串的next数组的时间复杂度为，每个元素的前面部分元素都需要检查前后是否相等，因此为
1/2*(1+m)*m/2=m(1+m)/4，因此为o(m2);
匹配阶段，每个主字符串位置移动，因此为o(n);
整个为o(m2+n);


KMP算法的Java实现：

package org.iaiai.suanfa;

/**
 * 
 * <p>
 * Title: KMP.java
 * </p>
 * <p>
 * E-Mail: [e-mail]
 * </p>
 * <p>
 * QQ: 176291935
 * </p>
 * <p>
 * Http: iaiai.iteye.com
 * </p>
 * <p>
 * Create time: 2011-8-5
 * </p>
 * 
 * @author 丸子
 * @version 0.0.1
 */
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) {
				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)) {
				if (j == 0) {
					index = i;
				}

				i++;
				j++;
			} else {
				// 一直寻找next，知道和当前元素不相等的元素，将其下标赋值给j
				int newj = this.next[j];
				while ((newj != -1)
						&& (this.p.charAt(newj) == this.p.charAt(j))) {
					newj = this.next[newj];
				}
				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 = "abacsbababbcacs";
		String p = "ab";
		KMP m = new KMP(s, p);

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

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

}