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;
	}

}