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

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 }
分享到 :
相关推荐