字元串比對----KMP算法

字元串比對KMP算法java代碼實作：

比對傳回字元串的開始下标，未比對傳回-1

public class KMPStringMatch {

	public static void main(String[] args) {
//		String var1 = "abccabcdabcf";
//		String var2 = "abcd";
		String var1 = "abccabcababcf";
		String var2 = "abcab";
		int[] nextArr = getNextArrByString(var2);
		int result = kmpStringMatch(var1, var2);
		System.out.println(result);
	}
	
	private static int kmpStringMatch(String var1,String var2) {
		
		int[] nextArr = getNextArrByString(var2);
		int slen = var1.length();
		int plen = var2.length();
		int i = 0;
		int j =0;
		while(i < slen && j < plen) {
			if(j == -1 || var1.charAt(i) == var2.charAt(j)) {
				i++;
				j++;
			}else {
				j = nextArr[j];
			}
		}
		if(j==plen) {
			return i-j ;
		}
		return -1;
	}

	private static int[] getNextArrByString(String var2) {
		
		int[] resultArr = new int[var2.length()];
		int k = -1;
		int i = 0 ;
		resultArr[0] = -1;
		while(i < var2.length()-1) {
			if(k == -1 || var2.charAt(i)==var2.charAt(k)) {
				k ++ ;
				i++;
				resultArr[i] = k;
			}else {
				k = resultArr[k];
			}
		}
		return resultArr;
	}
}