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 。

  举个例子:

KMP算法中我对获取next数组的理解

  怎么去找到模式串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 }
上一篇:算法总结篇---KMP算法


下一篇:google gson