KMP算法的原理就是利用相匹配的前缀子串与后缀子串，，来确定失配时下次对齐的位置；
其中最关键的就是next数组的确立；
数据结构课本上KMP算法next数组计算经典的例子：
void getNext(const char *pStr, int *nextArr){int i = 0, k = -1, pLen = strlen(pStr);nextArr[i] = k;int mLen = pLen – 1;while (i < mLen){if (k == -1 || pStr[i] == pStr[k]){nextArr[++i] = ++k;}else k = nextArr[k];}}而这个KMP算法next数组计算只关注了前k-1个字符中，前后匹配的子串，没有利用到当前失配的字符；
比如：ABACA，当第2个A失配时，说明被匹配串的当前位置的字符必定不等于A，所以将第0位对齐到此位也必定失配，所以应该继续回溯到第0位失配时所需要对齐的位，这里也就是-1；
这个"必定不等于(!=)"是可以被利用的！我们对KMP算法next数组计算的优化正是基于此；
废话不多说，下面是优化后的KMP算法next数组计算与注释：
//优化过后的next数组求法void getNext(const char *pStr, int *nextArr){int j = 0, j_next = -1, pLen = strlen(pStr);nextArr[j] = j_next;//此处第0位失配，则对齐第-1位；int mLen = pLen – 1;while (j < mLen){//基于第j位与第j_next已经相等（或者j_next为-1）//广义地将空字符（pStr[-1]）看做可以与任意字符相等，这样很益于理解//求下一个j失配时的对齐位if (pStr[++j] != pStr[++j_next]){//因为（自增++之后）pStr[j]与pStr[j_next]不相等//所以此时pStr[j]失配后，可以用pStr[j_next]来试试，所以nextArr[j] = j_next;nextArr[j] = j_next;//因为此时pStr[j]与pStr[j_next]不相等//所以回溯取pStr[j_next]失配时的对齐位pStr[nextArr[j_next]]//直到相等为止while (j_next != -1 && pStr[j] != pStr[j_next]) j_next = nextArr[j_next];}//这里就是优化点//因为（自增++之后）pStr[j]与pStr[j_next]相等//所以pStr[j]失配后，pStr[j_next]也必定失配//故丢弃pStr[j_next]，再取pStr[j_next]失配时的对齐位pStr[nextArr[j_next]]//也即nextArr[j] = nextArr[j_next];else nextArr[j] = nextArr[j_next];}}
给个无注释纯净版的（KMP算法next数组计算）：
void getNext(const char *pStr, int *nextArr){int j = 0, j_next = -1, pLen = strlen(pStr);nextArr[j] = j_next;int mLen = pLen – 1;while (j < mLen){if (pStr[++j] != pStr[++j_next]){nextArr[j] = j_next;while (j_next != -1 && pStr[j] != pStr[j_next]) j_next = nextArr[j_next];}else nextArr[j] = nextArr[j_next];}}
欢迎拍砖与指正！
版权声明：本文为博主原创文章，未经博主允许不得转载。
勤奋，它是一块可以吸引到一切美好事物的天然磁石，它比黄金珍贵，
