KMP算法（简略的说）

package algorithm;
//字符串匹配类
public class StringMatcher {
	
	//朴素字符串匹配,t:要匹配的目标字符串,pattern:匹配的模式字符串
	public static int navieMatch(String t,String pattern){
		int len1 = t.length();
		int len2 = pattern.length();
		for (int i = 0; i <= len1-len2; i++) {
			int j = 0;//每次都设置patter从头开始匹配
			int k = i;//保存当前t的偏移量
			//第一个字符匹配成功，才开始之后的匹配
			while(t.charAt(k++) == pattern.charAt(j++)){
				//匹配成功
				if (j == len2) {
					return i;
				}
			}
		}
		return -1;
	}
	
	//根据模式pattern得到next数组
	public static int[] getNext(String pattern){
		int len = pattern.length();
		int[] next = new int[len];
		//第一个next为0
		next[0] = 0;
		for(int i = 1 ; i < len; i++){
			//k表示之前的对称性
			int k = next[i-1];
			/*
			 *不断递归判断是否子对称 
			 * k等于0时，说明不再存在子对称
			 * pattern[k]不等于pattern[i]，说明子对称的后面的一个字符和当前字符不相等，所以继续递推
			 * 这些都不满足直接进行单个字符比较的条件
			 * */
			while (k != 0 && pattern.charAt(k) != pattern.charAt(i)) {
				k = next[k-1];//向前找子对称的子对称
			}
			if( pattern.charAt(i) == pattern.charAt(k))//找到了这个子对称，或者是直接继承了前面的对称性，这两种都在前面的基础上++
	              next[i]=k+1;
	         else
	              next[i]=0;       //如果遍历了所有子对称都无效，说明这个新字符不具有对称性，清0
		}
		return next;
	}
	
	public static int kmpMatch(String t,String pattern){
		int[] next = getNext(pattern);
		int len1 = t.length();
		int len2 = pattern.length();
		for (int i = 0; i <= len1-len2; ) {
			int j = 0;//每次都设置patter从头开始匹配
			int k = i;//保存当前t的偏移量
			//第一个字符匹配成功，才开始之后的匹配
			while(t.charAt(k++) == pattern.charAt(j++)){
				//匹配成功
				if (j == len2) {
					return i;
				}
			}
			i += i - next[i] + 1;
		}
		return -1;
	}
	
	public static void main(String[] args) {
		System.out.println(navieMatch("abcabaabcabac","abaa"));
		int[] next = getNext("ababaca");
		for(int i : next){
			System.out.print(i+" ");
		}
		System.out.println();
		System.out.println(kmpMatch("abcabaabcabac","abaa"));
	}
	
	
	
	
	
}