package net.yk.string;public class KMP {	public static void main(String[] args) {		String major = "abababcabcabcda";		String mode = "abcd";		int[] next = new KMP().next(mode);		System.out.println(new KMP().index_KMP(major, mode, 1, next));	}	/**	 * 	 * @param str	 * @return	 */	int[] next(String str) {		// 获取模式串的长度		int len = str.length();		// 创建字符数组用来存储模式串		char[] mode = new char[len + 1];		int[] next = new int[len + 1];		// 将模式串拷贝到字符数组中，从下标1开始		str.getChars(0, len, mode, 1);		int i = 1, j = 0;		next[1] = 0;		while (i < len) {			if (j == 0 || mode[i] == mode[j]) {				i++;				j++;				next[i] = j;			} else				j = next[j];		}		return next;	}			/**	 * next函数修正值算法	 * @param mode	 * @return	 */	int[] getNextVal(String mode) {		int len = mode.length();		char[] chars = stringToChar(mode);		int[] nextval = new int[len + 1];		// 求模式串mode的next函数修正值并存入数组nextval		int i = 1, j = 0;		nextval[1] = 0;		while(i < len){			if(j==0|| chars[i] == chars[j]){				++i;++j;				if(chars[i] != chars[j]) nextval[i] = j;				else nextval[i] = nextval[j];			}			else j = nextval[j];		}				return nextval;	}	char[] stringToChar(String mode) {		int len = mode.length();		char[] chars = new char[len + 1];		mode.getChars(0, len, chars, 1);		return chars;	}			/**	 * KMP 算法	 * 	 * @param major	 * @param mode	 * @param pos	 * @param next	 * @return	 */	int index_KMP(String major, String mode, int pos, int[] next) {		int majorL = major.length();		int modeL = mode.length();		//从下标1开始存储数据		char majorChar[] = new char[majorL + 1];		char modeChar[] = new char[modeL + 1];		major.getChars(0, majorL, majorChar, 1);		mode.getChars(0, modeL, modeChar, 1);		int i = pos, j = 1;		while (i <= majorL && j <= modeL) {			if (j == 0 || majorChar[i] == modeChar[j]) {				++i;				++j;			} else				j = next[j];		}		if (j > modeL) {			return i - modeL;		} else			return 0;	}}