KMP算法中我对获取next数组的理解
之前在学KMP算法时一直理解不了获取next数组的函数是如何实现的，现在大概知道怎么一回事了，记录一下我对获取next数组的理解。
KMP算法实现的原理就不再赘述了，先上KMP代码：
1 void getNext(char *pat, int *next) { 2 next[0] = -1; 3 int m = strlen(pat); 4 for (int i = 1; i < m; i++) { 5 int j = next[i - 1]; 6 while (j != -1 && pat[j] != pat[i - 1]) { 7 j = next[j]; 8 } 9 next[i] = j + 1; 10 } 11 } 12 13 int KMP(char *str, char *pat) { 14 int n = strlen(str), m = strlen(pat); 15 int next[m]; 16 getNext(pat, next); 17 18 int i = 0, j = 0; 19 while (i < n && j < m) { 20 if (j == -1 || str[i] == pat[j]) i++, j++; 21 else j = next[j]; 22 } 23 24 return j == m ? i - j : -1; 25 }
先说明，为了描述更清晰，我特意在主串和模式串后面紧接str，pat，s，p等标识，以区分不同的主串和模式串。
我对next数组的定义是这样的，next[j]存放的值是模式串pat的某个位置，而这个位置是：在匹配过程中，模式串pat在 j 这个位置发生失配时，接下来要与主串str进行匹配的位置。也就是说next[j]存放的值是模式串pat在 j 这个位置发生失配时回退到的位置，然后从这个位置开始继续与主串str比较。
而根据KMP算法的定义，当发生失配时，主串的指针 i 不需要移动，而只需要移动模式串pat的指针 j 。这是因为主串str和模式串pat有部分是相同的，也就是在模式串pat中，next[j]这个位置之前的部分（不包括next[j]这个位置）和主串str在 i 位置之前对应的部分（不包括i这个位置）是相同的。
而要获取模式串pat每个位置对应的next值，一个很重要的思想是，把模式串pat既看作是主串s，也看作是模式串p。这里所说的主串s和模式串p都是指同一字符串——模式串pat。
所以如果我们要获取模式串pat中某个位置 i 的next值，可以理解为当模式串pat在 i 这个位置发生失配时，应该回退到的那个位置，也就是next[i]这位置。
这时，我们把模式串pat从 0 到 i 这部分暂时理解为主串s，然后把模式串pat最前面的部分也就是从 0 到某个位置 j （其中j < i – 1）这部分理解为模式串p。我们要得到next[i]，就要知道 j 这个位置，使得模式串p从位置 0 到 j ，与主串s从位置 i – 1 开始之前的相同数量（j + 1）的那部分完全匹配。也就是满足 p0 p1 … pj == si-1-j si-j … si-1 。所以，在匹配时，当模式串pat在 i 这个位置发生失配，就可以回退到 j + 1 这个位置，再从 j + 1 这个位置继续与主串str比较。这样，就知道 next[i] = j + 1 。
举个例子：
怎么去找到模式串p中 j 那个位置呢？其实很简单，一开始就为 j 赋初值 j = next[i – 1] 。这里再重复一遍，next[i – 1]是模式串pat在 i – 1 这个位置发生失配时，应该回退到的位置。接着我们比较判断模式串pat在 i – 1 这个位置的字符是否与在 j 这个位置的字符相同。也就是主串s在 i – 1 这个位置是否与模式串p在 j这个位置的字符相同。即 pat[i – 1] == pat[j] ? 或是 s[i – 1] == p[j] ? 。
如果相同，那么直接就有 next[i] = j + 1 。否则我们可以理解为模式串p在 j 这个位置发生失配，就要进行回退。回退到哪里呢？当然是回退到next[j]了。所以说，如果发生失配，模式串p的指针j就一直回退，即有 j = next[j] ，直到满足i – 1这个位置与j这个位置的字符相同，才停止回退匹配，然后同样有会 next[i] = j + 1 。
想一下，如果在回退的过程中，始终没有发现匹配成功的情况，难道一直这样回退下去吗？答案肯定不是的。我们有个终止条件，就是一开始就规定 next[0] = –1 ，意味着当在模式串pat在 0 这个位置，都与不能够与主串str匹配，那么就没有再可以回退的位置了，这时主串str的指针与模式串pat的指针都要向后移动1位，然后继续匹配。
所以当发现 j == –1 时，就停止回退，说明当模式串pat在 i 这个位置发生失配时，只能够回退到 0 这个位置继续与主串str匹配。同时让主串s指针 i 与模式串p指针 j 同时向后移动1位。这时主串s指针在 i + 1 这个位置，模式串p指针在 j + 1 这个位置，也就是 0 这个位置，然后继续求后面位置的next值。
好了，现在我已经把我对KMP算法中获取next数组的理解表述完了，我们回到代码中看看。
1 void getNext(char *pat, int *next) { 2 next[0] = -1; // 一开始确定回退最终条件 3 int m = strlen(pat); 4 5 // 把模式串pat同时看作主串s和模式串p 6 for (int i = 1; i < m; i++) { // i就是主串s的指针 7 int j = next[i - 1]; // j就是模式串p的指针 8 9 // 我们就是要找到模式串p的某个位置j，使得模式串p从0到j这部分，与主串s从位置i - 1到前面的i - 1 - j的那部分完全匹配 10 while (j != -1 && pat[j] != pat[i - 1]) { // 只要j != -1，也就是还可以回退，同时与主串s的i - 1这个位置不匹配 11 j = next[j]; // j就一直回退 12 } 13 14 // 其中如果因为j == -1而退出循环，意味着找不到可以匹配的位置，则模式串pat在i这个位置发生失配时，只能够回退到最开始的位置0 15 next[i] = j + 1; // 不管最后是因为匹配成功还是无法回退而退出循环的，都有next[i] = j + 1 16 } 17 }
还有另外一种写法，是大多数人的写法，其实实现的原理与我上述的几乎相同，只不过代码写起来不同，效率也相差不多，只不过每轮循环时，下面的代码会比上面的代码少了次 j = next[i – 1] 的赋值操作。
1 void getNext(char *pat, int *next) { 2 next[0] = -1; 3 int m = strlen(pat); 4 5 // 这里的i并不是我们要求的next[i]中的那个i，而是要求next值那个位置的前一个位置 6 // 这里的j和上面代码的j相同，都是使得从0到j这部分，与从上面的那个i开始到i - j的那部分完全匹配 7 for (int i = 0, j = -1; i < m - 1; ) { // 由于这里的i是指要求next值那个位置的前一个位置，所以i最大为m - 2 8 9 // 如果发现匹配，就知道i的下一个位置i + 1的next值，也就是next[i + 1] = j + 1 10 // 如果j无法回退，i + 1的next值就为0，同样可以表示为next[i + 1] = j + 1 11 // 每次得到next[i + 1]，都会从++后的位置，也就是i + 1和j + 1这个位置继续接下来的匹配 12 if (j == -1 || pat[i] == pat[j]) next[++i] = ++j; 13 else j = next[j]; // 失配j就回退 14 } 15 }
