KMP算法

public int KMPSearch(String s, String m) {
	if (s == null || m == null || m.length() < 1 || s.length() < m.length()) {
		return -1;
	}
	char[] ss = s.toCharArray();
	char[] ms = m.toCharArray();
	int si = 0;
	int mi = 0;
	int[] next = getNextArray(ms); // next数组考虑的是除当前字符外的最长相同前缀后缀
	while (si < ss.length && mi < ms.length) {
		if (ss[si] == ms[mi]) {
			si++;
			mi++;
		}
		else if (next[mi] == -1) {
			si++;
		}
		else { // 如模式串中在mi处的字符跟文本串在si处的字符匹配失配时
			mi = next[mi]; // 下一步用next[mi]处的字符继续跟文本串si处的字符匹配
						   // 相当于模式串向右移动 mi - next[mi] 位
		}
	}
	return mi == ms.length ? si - mi : -1;
}


// ***cn-----***pos-1pos
public int[] getNextArray(char[] ms) {
	if (ms.length == 1) {
		return new int[] { -1 };
	}
	int[] next = new int[ms.length];
	next[0] = -1;
	next[1] = 0;
	int pos = 2;
	int cn = 0;
	while (pos < next.length) {
		if (ms[pos - 1] == ms[cn]) {
			next[pos++] = ++cn;
		}
		else if (cn > 0) {
			cn = next[cn];
		}
		else {
			next[pos++] = 0;
		}
	}
	return next;
}