学步园

1、计算返回字符串的next[]数组，2、查找字符串。

自己写了个恶心的，不知道有没有用。。。

	public static void main(String[] args) {

		 String textString = "ababadaababaaa";
		 String findString = "ababaaa";
		
		 System.out.println(findByNext(textString, findString));
		 System.out.println(textString.indexOf(findString));

	}

	private static void get_next(String T, int next[]) {
		int i = 1;
		int j = 0;
		next[1] = 0;
		while (i < T.length()) {
			if (j == 0 || T.charAt(i - 1) == T.charAt(j - 1)) {
				++i;
				++j;
				next[i] = j;
			} else {
				j = next[j];
			}
		}

	}

	private static int findByNext(String text, String find) {
		int r = 0;
		int next[] = new int[255];
		get_next(find, next);
		for (int i = 0; i <= (text.length() - find.length()); i++) {
			if (text.charAt(i) == find.charAt(0)) {
				for (int j = 1; j < find.length(); j++) {
					if (text.charAt(i + j) != find.charAt(j)) {
						j = find.length();
						i = i + next[j];// KMP算法将i的位置外后移，减少不必要的回溯
					} else if (j == find.length() - 1) {
						r = i;
						i = text.length();
						break;
					}
				}
			}
		}
		return r;
	}

虽然感觉和书上的比好像比书上的复杂多了，但起码这个是自己写的嘛- -，虽然不知道对不对。

顺带把书上的例子也贴上。

例子1

private static int indexKMP(String S, String T) {
		int i = 1;
		int j = 1;
		int next[] = new int[255];
		get_index(T, next);

		while (i < S.length() && j < T.length()) {
			if (j == 0 || S.charAt(i - 1) == T.charAt(j - 1)) {
				++i;
				++j;
			} else {
				j = next[j];
			}
		}
		if (j >= T.length()) {
			return i - T.length();
		} else {
			return 0;
		}
	}

例子2，改进后的KMP

private static void get_nextval(String T, int nextval[]) {
		int i = 1;
		int j = 0;
		nextval[1] = 0;
		while (i < T.length()) {
			if (j == 0 || T.charAt(i - 1) == T.charAt(j - 1)) {
				++i;
				++j;
				if (T.charAt(i - 1) != T.charAt(j - 1)) {
					nextval[i] = j;
				} else {
					nextval[i] = nextval[j];
				}
			} else {
				j = nextval[j];
			}
		}
	}