KMP算法解释：理解关于next[j]数组的求解问题

int IndexString(char* Original_string, char* Pattern_string) {
	int length_OriStr = strlen(Original_string);
	int length_PatStr = strlen(Pattern_string);
	for (int i = 0; i < length_OriStr; ) {//for循环相比while更加直观，两个终止条件均为不到字符串终点
		for (int j = 0; j < length_PatStr; ) {
			if (*(Original_string + i) == *(Pattern_string + j)) {
				i++;
				j++;
			}
			else {//失配
				j = 0;
				i = i - j + 1;
			}
			if (j == length_PatStr) {
				return i - j;//返回匹配的字符串在主串中第一个相同字符的下标。
			}
		}
	}
	return False;//未找到
}

#define True 1
#define False 0

typedef int status;

typedef struct {
	char* string;
	int length;
}HString;

status Getnext(int* next,HString Pattern_string) {//得到nextj数组
	if (next == NULL) {
		return False;
	}
	next[0] = -1;
	int k = next[0];//k用来存放对应next[j]
	int j = 0;
	while (j < Pattern_string.length-1) {
		//因为最后会有j++，所以要有length-1，否则超限；或者理解为每次都在求解当前位置对应下一位置的next[j]值，所以要-1
		if (k == -1 || *(Pattern_string.string + k) == *(Pattern_string.string + j)) {//没有匹配字符或当前两个字符相等
			j++;
			k++;
			next[j] = k;//后一个的nextj=前一个nextj+1
		}
		else {
			k = next[k];//回溯
		}
	}
	return True;
}

int Index(HString Original_string, HString Pattern_string) {
	int judge = -1;//标识符，默认模式串不存在
	int i = 0, j = 0;//i用来遍历主串，j用来跳转模式串
	int numx = 0;//用来保存每个第一次比较的字符在主串中的位置

	int* next = (int*)malloc(sizeof(int) * Pattern_string.length);//nextj数组
	if (next == NULL) {
		exit(1);
	}
	Getnext(next, Pattern_string);//调用上面的函数求得模式串next[j]数组

	for (i = 0; i < Original_string.length; ) {
		if (j==-1 || *(Original_string.string + i) == *(Pattern_string.string + j)) {
			i++;
			j++;
			if (j == Pattern_string.length) {//完全相同后跳出
				break;
			}
		}
		else {
			j = *(next+j);//跳转到next[j]对应位置
		}
	}
	if (j == Pattern_string.length) {
		judge = i - j + 1;//返回完全匹配后，模式串中第一个字母在主串第一次出现的次序（不是下标）
	}
	free(next);
	return judge;
}