编辑代码

class Main {
	public static void main(String[] args) {
        //JSRUN引擎2.0，支持多达30种语言在线运行，全仿真在线交互输入输出。
        String t = "abcabca";
        String s = "aaabbbcdabcabca";
        System.out.println(KMP(s,t));
		System.out.println("Hello world!   - java.jsrun.net ");
	}
	public static int[] getNext(String t) {
		int[] next = new int[t.length()];
		next[0] = -1;
		int suffix = 0;  // 后缀
		int prefix = -1;  // 前缀
		while (suffix < t.length() - 1) {
			//若前缀索引为-1或相等，则前缀后缀索引均+1
			if (prefix == -1 || t.charAt(prefix) == t.charAt(suffix)) {
				++prefix;
				++suffix;
				next[suffix] = prefix;  //1  
			} else {
				prefix = next[prefix];  //2
			}
		}
		return next;
	}
	public static int KMP(String s, String t) {
		int i = 0;
		int j = 0;
		//得到next数组
		int[] next = getNext(t);
		while (i < s.length() && j < t.length()) {
			if (j == -1 || s.charAt(i) == t.charAt(j)) {
				i++;
				j++;
			} else {
				//根据next数组的指示j进行回溯，而i永远不会回溯
				j = next[j];
			}
		}
		if (j == t.length()) {
			return i - j;
		} else {
			return -1;
		}
	}
}