KMP算法，查找子串

KMP.java

public class KMP {
	public static void main(String[] args) {
		String source = "ababababcaab";
		String target = "abababca";
		KMP kmp = new KMP();
		int[] result = kmp.preProcess(target);
		for(int i=0; i<result.length; i++) {
			System.out.println(result[i]);
		}
		System.out.println(kmp.kmp(source, target));
	}

	public boolean kmp(String source, String target) {
		int sourceLen = source.length();
		int targetLen = target.length();
		int[] next = preProcess(target);

		int j = 0;
		for(int i=0; i<sourceLen; i++) {
			while(j != 0 && source.charAt(i) != target.charAt(j)) {
				j = next[j - 1];
			}
			if(source.charAt(i) == target.charAt(j) ) {
				j++;
			}
			if(j == targetLen) {
				//if find all
				//j = next[j-1];
				return true;
			}
		}		
		return false;
	}

	public int[] preProcess(String s) {
		int size = s.length();
		int[] next = new int[size];

		next[0] = 0;
		int j = 0;
		for(int i=1; i<size; i++) {
			while(j != 0 && s.charAt(i) != s.charAt(j)) {
				j = next[j];
			}
			if(s.charAt(i) == s.charAt(j)) {
				j++;
			}
			next[i] = j;
		}
		return next;
	}
}

print:

0
0
1
2
3
4
0
1
true