Next数组
- 首先规定从串下标为j的字符前的子串的最大相等前后缀长度为k
- 我们已经知道，当主串与从串不匹配时，从串应该回退到下标为 j字符前子串的最长相等前后缀长度 的字符，而长度为length的从串（不包含结束符"\0"）有length个最长公共前后缀长度，我们规定，这length个数据都存在一个叫Next的数组中
- 例如串“abcababcabc”的Next数组为{-1,0,0,0,1,2,1,2,3,4,5}，如图
如何运用代码逻辑计算Next数组
- 显然，用肉眼看出一个字符串的Next数组是十分简单的，但计算机可是十分死板的，那我们怎么用计算机的思维（代码逻辑）来计算Next数组呢？
- 我们还是以字符串arr“abcababcabc”为例，分以下三种情况：
arr[j] == arr[k]
- 假设我们要计算Next[9]，其中我们已知Next[0]~Next[8] ：{-1,0,0,0,1,2,1,2,3}
- 我们可以发现当j = 8时，arr[j] = a， Next[j] = k = 3，arr[k] = a，即arr[j] = arr[k]，又因为我们已知arr[j]前子串的最长公共前后缀长度为k = 3，那么我们就可以分析出，当arr[j] == arr[k]时，Next[j + 1] = k + 1，如图：
arr[j] != arr[k]
- 假设我们要计算Next[6]，其中我们知道Next[0]~Next[5] ：{-1,0,0,0,1,2}
- 当j = 5时，arr[j] = a，Next[j] = k = 2，arr[k] = c，即arr[j] != arr[k]
- 那么我们再令新的k = next[k] = 0（第一个k为新的k，第二个k还是旧的k，即Next[j]），此时arr[k] = arr[0] = a = arr[j]，这样又回到了上面arr[j] = arr[k]的条件，所以当arr[j] != arr[k]时，k就要不断回退，并被重新赋值（回退到位置就是arr[k]，被赋予的值就是Next[k]），直到出现arr[j] = arr[k]的情况
特殊情况（k == -1）
- 出现了k == -1这种情况，就意味着k走到字符串的第一个元素也没有遇到arr[j] == arr[k]的情况，那么此时k就不能继续回退了，也就是说下标为j + 1元素前子串的最长公共前后缀长度为0，即arr[j + 1] = k + 1 = -1 + 1 = 0。
得到Next数组的函数GetNext
void GetNext(int *Next, char *str) { int len = strlen(str); //从串长度 int i = 1; //第一个待求项Next[i] int k = -1; //待求项前一个的k值 Next[0] = -1; //默认第一个值为-1 while(i < len) { if(k == -1 || str[i - 1] == str[k]) //arr[j] == arr[k]和k == -1 { Next[i] = k + 1; i++; //待求项右移 k++; //待求项前一个的k值加一 } else //arr[j] != arr[k] k = Next[k]; } }
运用Next数组实现KMP算法
- 我们来看一道具体的题目实现strStr
- 直接上代码
//得到Next数组的函数 void GetNext(int *Next, char *str) { int len = strlen(str); //从串长度 int i = 1; //第一个待求项Next[i] int k = -1; //待求项前一个的k值 Next[0] = -1; //默认第一个值为-1 while(i < len) { if(k == -1 || str[i - 1] == str[k]) //arr[j] == arr[k]和k == -1 { Next[i] = k + 1; i++; //待求项右移 k++; //待求项前一个的k值加一 } else //arr[j] != arr[k] k = Next[k]; } } //实现字符串查找 int strStr(char * haystack, char * needle){ int len_hay = strlen(haystack); int len_need = strlen(needle); int i = 0, j = 0; //如果从串长度大于主串长度，直接返回-1 if(len_need > len_hay) return -1; //如果主串从串长度都为0，直接返回0 if(len_hay == 0 && len_need == 0) return 0; int *Next = (int *)malloc(sizeof(int) * len_need); //为Next数组申请内存 GetNext(Next,needle); //得到Next数组 while(i < len_hay && j < len_need) { if(haystack[i] == needle[j]) { i++; j++; } //当j还未回溯到第一个字符 //且从串与主串开始不匹配时，j开始回溯 else if(j != 0) j = Next[j]; //如果j已经回溯到第一个字符，那么就让主串i向右走一个字符，继续匹配 else i++; } //如果j大于等于从串长度，说明j已经走到了从串为，说明匹配完成，返回主串开始匹配的位置 if(j >= len_need) return i - j; return -1; }
对KMP算法的改进
引例：
- 我们先来看一个例子：
- 主串为“aaaabcab”，从串为“aaaac”，匹配过程如图：
- 我们可以发现在这一个匹配过程中，第二步，第三步，第四步其实是多余的，为什么呢？我们可以看到第一步中字符b和字符c不匹配时，字符c回溯到字符a，显然字符a仍然不和字符b匹配，但字符a回溯后的字符还是a，自然不能和字符b匹配，这样就造成了许多重复比较的情况，因此我们就是要减少这种重复比较来改善KMP算法。
改善方法
- 通过上述例子，我们知道了，出现重复比较的原因是当主串字符和从串字符出现不匹配时，从串字符的回溯字符仍等于原来的字符（arr[j] = arr[k]）
- 因此我们就要阻止这种情况的出现，若从串字符的回溯字符仍等于从串字符，那么就要继续回溯（next[i] = next[k]），直到出现不相等的情况或回溯到了从串头
- 自然，我们对next数组的求法也要做出改变。
- 例如字符串“ababaaab”的next数组为{-1,0,-1,0,-1,3,1,0}
实现代码
//得到新的Next数组Nextval void GetNextVal(int* nextval, char *str) { int len = strlen(str); int k = -1; int i = 0; nextval[0] = -1; //第一个k值默认为-1 //由于操作是先++后赋值，因此为了不会数组越界，i < len - 1 while (i < len - 1) { if (k == -1 || str[i] == str[k]) { i++; k++; //相比于最开始的KMP算法，多出来的就是这个if判断 //如果回溯字符等于原字符，那么就要继续回溯，避免重复比较 if (str[i] == str[k]) nextval[i] = nextval[k]; //如果回溯字符不等于原字符，那么就和原来的操作一样 else nextval[i] = k; } else k = nextval[k]; } } int strStr(char* hayStack, char* needle) { int len_h = strlen(hayStack); int len_n = strlen(needle); int i = 0, j = 0; int *NextVal = (int*)malloc(sizeof(int) * len_n); GetNextVal(NextVal, needle); while (i < len_h && j < len_n) { if (hayStack[i] == needle[j]) { i++; j++; } else if (j != 0) { j = NextVal[j]; //相比于原来的KMP算法，多出了这一句if判断 //这是由于新的NextVal数组由于k的多次回溯，会出现不止第一个字符的k为-1的情况，因此为防止数组越界，当j为-1时要将其置为零 if (j == -1) j = 0; } else i++; } if (j >= len_n) return i - j; else return -1; }
