字符串_KMP

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

对于一个字符串，从第二个开始寻找他的最大相同前后缀，实现代码为以上部分，对于连续的前后缀只需要next[i-1]+1便可以获得当前字符的next序列，如果当前字符在期望的相同前后缀中找不到对应的字符（即T[I]!=T[j]）则返回j=next[j-1],再对T[j]与T[I]进行判断，向前寻找是否存在一个相同前后缀；

int Index_KMP (String S, String T, int next[]){    //S为长串，T为短串
	int i = 1, j = 1;
	while (i <= S.length && j <= T.length){
		if (j == 0 || S.ch[i] == T.ch[j]){
			++ i; ++ j;
		}
		else
			j = next[j];
	}
	if (j > T.length)
		return i - T.length;
	else 
		return 0;
}

从主串的头开始进行判断，当副串的的字符与主串的字符不对应时，找到副串该字符位置对应的next表，副串对应主串的位置跳跃next表对应的单位字符，再次从跳跃位置开始继续对应，反复上述操作，直到找到主串中能够与副串完全匹配的字符串的位置