devbox
正经夜光杯
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

字符串模式匹配的KMP算法中next数组计算方法详解_kmp算法next计算方法

作者：正经夜光杯 | 2024-07-18 21:12:10

赞

踩

kmp算法next计算方法

使用KMP算法匹配字符串的关键就是正确计算出next数组(不清楚何为模式匹配，何为KMP算法，什么是next数组可以自行百度或参考数据结构教科书)。next数组的计算是一大难点，殷人昆的数据结构教科书中对此问题的论述不够清晰，所列代码和说明部分关联性不强，看了让人似懂非懂。自己花了很长时间琢磨next数组计算的问题，现在总算从头到尾弄明白了，于是就在这里将自己的思考所得与大家分享。

         现有长为M的模式串P=a0 a1 —– aM-1,记P在索引i，j之间的部分(包括i,j)为P[i,j],要求模式串P[0,M-1]的next数组的各元素next[0]—-next[M-1]。

      首先next[0]=-1(为什么取-1下面有说明),根据next数组的定义，对j>=1,next[j]为串P[0,j-1]的最长相等前后缀子串的长度(对串b0,b1,–,bn,满足b0,–,bk=bn-k,–,bn-1,bn 0<=k<n 的所有相等前后缀子串中的最长者b0,–,bk和bn-k,–,bn-1,bn即为串b0,b1,–,bn的最长相等前后缀子串，其长度为k+1)，若串P[0,j-1]不存在相等的前后缀子串(当然也就不存在最长相等前后缀子串)则令next[j]=0。

      由于我们最先知道next[0]=-1,所以自然就可以考虑在next[0],—,next[j]已知的情况下推算next[j+1]的值，我们来看下图：

这幅图可以给我们一些启发。如图所示，假定j>=1,我们先考虑K1=next[j],若K1=0，则串P[0,j-1]中不存在相等前后缀子串，这意味着串P[0,j]中不存在长度大于2小于等于j的相等前后缀子串，因为假若存在，去掉前缀最后一个元素和后缀最后一个元素P[j]，剩下的部分刚好是串P[0,j-1]的一对相等前后缀子串，矛盾。于是串P[0,j]唯一可能存在的相等前后缀子串只能是p[0]和p[j]，下面我们检查是否有p[0]=p[j],若是则p[0]和p[j]就是串P[0,j]唯一的相等前后缀子串，因而就为串P[0,j]的最大相等前后缀子串，其长度为1，故next[j+1]=1.若不是,则说明p[0,j]中不存在相等前后缀子串，从而next[j+1]=0,如果K1！=0，则K1就为串P[0,j-1]的最长相等前后缀子串A1，B1的长度，也是A1最末元素下一位置的索引。我们检查P[K1]是否和P[j]匹配，若匹配则A1和P[K1]构成的子串和B1和P[j]构成的子串就是串P[0,j]的最长相等前后缀子串，这是因为假若还存在更长的串P[0,j]的相等前后缀子串，去掉前缀最末元素和后缀最末元素P[j]，则剩下的部分刚好是串P[0,j-1]的一对相等前后缀子串，其长度大于A1，B1矛盾。于是串P[0,j]的最长相等前后缀子串的长度就是K1+1,因而next[j+1]=K1+1,这样我们就求出了next[j+1].如果P[K1]和P[j]不匹配,我们令K2=next[K1],若K2=0，则A1中不存在相等前后缀子串，于是串P[0,j-1]中不存在比A1,B1更小的相等前后缀子串，因为如果存在，则后缀与前缀构成了A1的相等前后缀子串，矛盾。这样A1，B1构成了串P[0,j-1]的唯一的相等前后缀子串，但P[K1]和P[j]不匹配，故串P[0,j]中不存在长度大于2小于等于j的相等前后缀子串，因为假若存在，去掉前后缀最末元素得到串P[0,j-1]的一对相等前后缀子串，它只能是A1，B1，但假设存在的P[0,j]中长度大于2小于等于j的相等前后缀子串的前缀和后缀的最末元素相互匹配，于是A1，B1下一位置上的元素相互匹配，即P[K1]和P[j]匹配，矛盾。这样串P[0,j]唯一可能存在的相等前后缀子串只能是p[0]和p[j]，下面我们检查是否有p[0]=p[j],若是则p[0]和p[j]就是串P[0,j]唯一的相等前后缀子串，因而就为串P[0,j]的最大相等前后缀子串，其长度为1，故next[j+1]=1.若不是,则说明p[0,j]中不存在相等前后缀子串，从而next[j+1]=0，若K2！=0，则K2就是A1的最长相等前后缀子串A2，C2的长度，也是A2最末元素下一位置的索引.C2在B1中有相应的镜像B2，则A2，B2构成了串P[0,j-1]第二长的相等前后缀子串，这是因为假若A2，B2不是串P[0,j-1]第二长的相等前后缀子串，那么必有串P[0,j-1]的相等前后缀子串，其长度介于A1，B1和A2，B2之间，其前后缀构成了A1的一对相等前后缀子串，注意其长度长于A2，B2和A2，C2，于是矛盾。下面我们检查P[K2]是否和P[j]匹配，若匹配，则A2和P[K2]构成的子串和B2和P[j]构成的子串就是串P[0,j]的最长相等前后缀子串，这是因为假若还存在更长的串P[0,j]的相等前后缀子串，去掉前缀最末元素和后缀最末元素P[j]，则剩下的部分刚好是串P[0,j-1]的一对相等前后缀子串，其长度大于A2，B2，因而它只能是A1，B1，注意我假设存在的更长的串P[0,j]的相等前后缀子串的前后缀的最末元素相互匹配，因此A1，B1的下一位置的元素相互匹配，即P[K1]和P[j]相互匹配，矛盾。这样串P[0,j]的最长相等前后缀子串的长度就是K2+1,因而next[j+1]=K2+1,这样我们就求出了next[j+1].如果P[K2]和P[j]不匹配,我们令K3=next[K2],若K3=0，则A2中不存在相等前后缀子串，于是串P[0,j-1]中不存在比A2,B2更小的相等前后缀子串，因为如果存在，则后缀与前缀构成了A2的相等前后缀子串，矛盾。注意P[K2]和P[j]不匹配，故串P[0,j]中不存在长度大于2小于等于j的相等前后缀子串，因为假若存在，去掉前后缀最末元素得到串P[0,j-1]的一对相等前后缀子串，它只能是A1,B1和A2，B2中的一个，而我假设存在的串P[0,j]中长度大于2小于等于j的相等前后缀子串的前缀后缀的最末元素相互匹配，这意味着A1，B1和A2，B2中必有一个其前后缀的最末元素的下一位置上的元素相互匹配，这和P[K2]和P[j]以及P[K1]和P[j]不匹配矛盾。这样串P[0,j]唯一可能存在的相等前后缀子串只能是p[0]和p[j]，下面我们检查是否有p[0]=p[j],若是则p[0]和p[j]就是串P[0,j]唯一的相等前后缀子串，因而就为串P[0,j]的最大相等前后缀子串，其长度为1，故next[j+1]=1.若不是,则说明p[0,j]中不存在相等前后缀子串，从而next[j+1]=0，若K3！=0，则K3就是A2的最长相等前后缀子串A3，C3的长度，也是A3最末元素下一位置的索引.C3在B2中有相应的镜像B3，则A3，B3构成了串P[0,j-1]第三长的相等前后缀子串，这是因为假若A3，B3不是串P[0,j-1]第三长的相等前后缀子串，那么必有串P[0,j-1]的相等前后缀子串，其长度介于A2，B2和A3，B3之间，其前后缀构成了A2的一对相等前后缀子串，注意其长度长于A3，B3和A3，C3，于是矛盾。下面我们检查P[K3]是否和P[j]匹配，若匹配，则A3和P[K3]构成的子串和B3和P[j]构成的子串就是串P[0,j]的最长相等前后缀子串，这是因为假若还存在更长的串P[0,j]的相等前后缀子串，去掉前缀最末元素和后缀最末元素P[j]，则剩下的部分刚好是串P[0,j-1]的一对相等前后缀子串，其长度大于A3，B3，因而它只能是A1，B1，A2，B2中的一个，注意我假设存在的更长的串P[0,j]的相等前后缀子串的前后缀的最末元素相互匹配，因此A1，B1,A2，B2中必有一个其前缀后缀的最末元素的下一位置上的元素相互匹配，这和P[K2]和P[j]以及P[K1]和P[j]不匹配矛盾。这样串P[0,j]的最长相等前后缀子串的长度就是K3+1,因而next[j+1]=K3+1,这样我们就求出了next[j+1].如果P[K3]和P[j]不匹配,我们令K4=next[K3]，若K4=0………………

         ……………………我们令Km=next[Km-1],若Km=0，则Am-1中不存在相等前后缀子串，于是串P[0,j-1]中不存在比Am-1,Bm-1更小的相等前后缀子串，因为如果存在，则后缀与前缀构成了Am-1的相等前后缀子串，矛盾。注意P[Km-1]和P[j]不匹配，故串P[0,j]中不存在长度大于2小于等于j的相等前后缀子串，因为假若存在，去掉前后缀最末元素得到串P[0,j-1]的一对相等前后缀子串，它只能是A1,B1,A2，B2,…………Am-1,Bm-1中的一个，而我假设存在的串P[0,j]中长度大于2小于等于j的相等前后缀子串的前缀后缀的最末元素相互匹配，这意味着A1，B1,A2，B2,…………Am-1,Bm-1中必有一个其前后缀的最末元素的下一位置上的元素相互匹配，这和P[K1]和P[j],P[K2]和P[j],…………,P[Km-1]和P[j]不匹配矛盾。这样串P[0,j]唯一可能存在的相等前后缀子串只能是p[0]和p[j]，下面我们检查是否有p[0]=p[j],若是则p[0]和p[j]就是串P[0,j]唯一的相等前后缀子串，因而就为串P[0,j]的最大相等前后缀子串，其长度为1，故next[j+1]=1.若不是,则说明p[0,j]中不存在相等前后缀子串，从而next[j+1]=0，若Km！=0，则Km就是Am-1的最长相等前后缀子串Am，Cm的长度，也是Am最末元素下一位置的索引.Cm在Bm-1中有相应的镜像Bm，则Am，Bm构成了串P[0,j-1]第m长的相等前后缀子串，这是因为假若Am，Bm不是串P[0,j-1]第m长的相等前后缀子串，那么必有串P[0,j-1]的相等前后缀子串，其长度介于Am-1，Bm-1和Am，Bm之间，其前后缀构成了Am-1的一对相等前后缀子串，注意其长度长于Am，Bm和Am，Cm，于是矛盾。下面我们检查P[Km]是否和P[j]匹配，若匹配，则Am和P[Km]构成的子串和Bm和P[j]构成的子串就是串P[0,j]的最长相等前后缀子串，这是因为假若还存在更长的串P[0,j]的相等前后缀子串，去掉前缀最末元素和后缀最末元素P[j]，则剩下的部分刚好是串P[0,j-1]的一对相等前后缀子串，其长度大于Am，Bm，因而它只能是A1，B1，A2，B2,…………,Am-1,Bm-1中的一个，注意我假设存在的更长的串P[0,j]的相等前后缀子串的前后缀的最末元素相互匹配，因此A1，B1,A2，B2,…………,Am-1,Bm-1中必有一个其前缀后缀的最末元素的下一位置上的元素相互匹配，这和P[K1]和P[j],P[K2]和P[j],…………,P[Km-1]和P[j]不匹配矛盾。这样串P[0,j]的最长相等前后缀子串的长度就是Km+1,因而next[j+1]=Km+1,这样我们就求出了next[j+1].如果P[Km]和P[j]不匹配,我们令Km+1=next[Km]，若Km+1=0………………

    以此类推，按照上述步骤不断进行下去，注意到j>K1>K2>……>Km>…… 所以我们在上述过程中得到的前缀子串A1,A2,——-,Am—-的长度严格递减，由于长度不能为负，所以上述过程不可能无限进行下去，必然在有限步后终止。也就是说，在操作有限步后，要么遇到下图所示的情况：

这里我们最终得到串P[0,j-1]的最短相等前后缀子串An,Bn,但p[Kn]和P[j]无法匹配,于是仿照以上分析令Kn+1=next[Kn],由于An,Bn为最短相等前后缀子串，所以这里必有Kn+1=0.这样我们检查p[0]和p[j]是否相等，若是则next[j+1]=1,否则next[j+1]=0。这样next[j+1]就求出了。

要么遇到下图所示情况：

这里我们最终得到串P[0,j-1]的第m长相等前后缀子串Am,Bm，p[Km]和P[j]能够相互匹配，根据以上分析知next[j+1]=Km+1,这样next[j+1]就求出了。

要么遇到下图所示情况：

按照以上分析，此时检查P[0]和P[j]是否相等，若是则next[j+1]=1,否则next[j+1]=0,这样next[j+1]就求出了。

综上，可以总结出在已知next[0],next[1],—,next[j]的情况下计算next[j+1]的算法如下(j>=1):

(1)将j赋值给k

(2)如果next[k]等于0：

         <1>如果模式串在索引0处的字符和在索引j处的字符匹配：1赋值给next[j+1]

               如果模式串在索引0处的字符和在索引j处的字符不匹配：0赋值给next[j+1]

         <2>算法结束

    如果next[k]不等于0：

          <1>如果模式串在索引next[k]处的字符和在索引j处的字符匹配：

                 {1} next[k]加一赋值给next[j+1] 

                 {2} 算法结束

                如果模式串在索引next[k]处的字符和在索引j处的字符不匹配：

                 {1}next[k]赋值给k

                 {2}转(2)               

上述用自然语言描述的算法的JAVA代码是(pat表示模式串P)：

  1. int k=j;  
  2. while(true)  
  3. {  
  4.     if (next[k]==0)  
  5.     {  
  6.         if (pat.charAt(0)==pat.charAt(j))  
  7.             next[j+1]=1;  
  8.         else  
  9.             next[j+1]=0;  
  10.         break;  
  11.     }  
  12.     else  
  13.     {  
  14.        if (pat.charAt(next[k])==pat.charAt(j))  
  15.        {  
  16.            next[j+1]=next[k]+1;  
  17.            break;  
  18.        }  
  19.        else  
  20.        {  
  21.            k=next[k];  
  22.        }  
  23.     }  
  24. }

以上在已知next[0],next[1],–,next[j]的情况下求next[j+1]的代码对j>=1是适用的，但在j=0时(即已知next[0]求next[1])无效，因为以上代码在首次进入循环后运行到11行时出现了pat.charAt(-1)这样的字符串越界访问，解决这个问题也很简单，把11行改写为

if (next[k]==-1 || pat.charAt(next[k])==pat.charAt(j))

就可以了。这样j=0时next[1]的值能正确求出(就是0),这也是为什么next[0]=-1的原因，因为此时若next[0]=-1,则next[1]的值就能正确求出。此外这样改写对j>=1时next[j+1]的求解没有任何影响，这是因为j>=1时代码运行到11行时表达式next[k]==-1的值总为false,这样

if (next[k]==-1 || pat.charAt(next[k])==pat.charAt(j))

等价于

if (pat.charAt(next[k])==pat.charAt(j))

匹配判断是能够正常进行的

现在我们可以写出完整的计算next数组的代码了:

代码一

  1. package nextcompute;  
  2. import java.util.*;  
  3.   
  4. public class nextcom  
  5. {  
  6.     public static void main(String[] args)  
  7.     {  
  8.         String pat;  
  9.         Scanner input=new Scanner(System.in);  
  10.         System.out.println("请输入模式串");  
  11.         pat=input.nextLine();  
  12.           
  13.         int[] next=new int[pat.length()];  
  14.         next[0]=-1;  
  15.         for (int j=0; j<pat.length()-1; j++)  
  16.         {  
  17.             int k=j;  
  18.             while(true)  
  19.             {  
  20.                 if (next[k]==0)  
  21.                 {  
  22.                     if (pat.charAt(0)==pat.charAt(j))  
  23.                         next[j+1]=1;  
  24.                     else  
  25.                         next[j+1]=0;  
  26.                     break;  
  27.                 }  
  28.                 else  
  29.                 {  
  30.                     if (next[k]==-1 || pat.charAt(next[k])==pat.charAt(j))  
  31.                     {  
  32.                         next[j+1]=next[k]+1;  
  33.                         break;  
  34.                     }  
  35.                     else  
  36.                     {  
  37.                         k=next[k];  
  38.                     }  
  39.                 }  
  40.             }  
  41.         }  
  42.           
  43.         for (int s: next)  
  44.         {  
  45.             System.out.print(s+" ");  
  46.         }  
  47.         System.out.println();  
  48.     }  
  49. }

程序将模式串读入String对象pat，然后计算pat对应的next数组。外层for循环的每一轮循环根据next数组前j+1个值计算next[j+1],内层while循环用于next[j+1]的具体计算

运行结果：

可以验证这是正确的

为了得到数据结构教科书上给出的简洁形式，我们还需要将代码一进行等价转换。设想，如果每次进入内层while循环前k=next[j],那么代码一20行，30行，32行的next[k]完全可以用k替换,第17行代码可以删除,代码一的k=next[k]保持不变，这是因为在代码一中执行k=next[k]后访问next[k]和在修改的代码中执行k=next[k]后访问k实际上是一样的，此外还需要保证内层while循环结束前(也就是next[j+1]算出时)k=next[j+1],j变为j+1(为下一轮计算next[j+2]作准备),因此代码一可以等价地改写如下：

代码二

  1. package nextcompute;  
  2. import java.util.*;  
  3.   
  4. public class nextcom2  
  5. {  
  6.     public static void main(String[] args)  
  7.     {  
  8.         String pat;  
  9.         Scanner input=new Scanner(System.in);  
  10.         System.out.println("请输入模式串");  
  11.         pat=input.nextLine();  
  12.           
  13.         int[] next=new int[pat.length()];  
  14.         int j, k;  
  15.         next[0]=-1; j=0; k=-1;  
  16.         while (j<pat.length()-1)  
  17.         {  
  18.             while(true)  
  19.             {  
  20.                 if (k==0)  
  21.                 {  
  22.                     if (pat.charAt(0)==pat.charAt(j))  
  23.                     {  
  24.                         next[j+1]=1;  
  25.                         j++;  
  26.                         k=1;  
  27.                     }  
  28.                     else  
  29.                     {  
  30.                         next[j+1]=0;  
  31.                         j++;  
  32.                         k=0;  
  33.                     }  
  34.                     break;  
  35.                 }  
  36.                 else  
  37.                 {  
  38.                     if (k==-1 || pat.charAt(k)==pat.charAt(j))  
  39.                     {  
  40.                         next[j+1]=k+1;  
  41.                         k++;  
  42.                         j++;  
  43.                         break;  
  44.                     }  
  45.                     else  
  46.                     {  
  47.                         k=next[k];  
  48.                     }  
  49.                 }  
  50.             }  
  51.         }  
  52.           
  53.         for (int s: next)  
  54.         {  
  55.             System.out.print(s+" ");  
  56.         }  
  57.         System.out.println();  
  58.     }  
  59. }

 注意初始条件

next[0]=-1; j=0; k=-1;

j=0是因为要先由next[0]推算next[1],再由next[0],—,next[j]推算nextj+1,k=-1是因为首次进入外层while循环后第一次进入内层while循环前k应等于next[0]==-1

可以验证代码二的运行结果和代码一是一样的

进一步分析代码二可以发现，代码二中内层嵌套的while循环，34行43行的break完全可以去掉，并且24-26行，30-32行，40-42行可以写成更紧凑的形式，这样我们可以把代码二改写成等价的代码三:

代码三

  1. package nextcompute;  
  2. import java.util.*;  
  3.   
  4. public class nextcom3  
  5. {  
  6.     public static void main(String[] args)  
  7.     {  
  8.         String pat;  
  9.         Scanner input=new Scanner(System.in);  
  10.         System.out.println("请输入模式串");  
  11.         pat=input.nextLine();  
  12.           
  13.         int[] next=new int[pat.length()];  
  14.         int j, k;  
  15.         next[0]=-1; j=0; k=-1;  
  16.         while (j<pat.length()-1)  
  17.         {  
  18.             if (k==0)  
  19.             {  
  20.                 if (pat.charAt(0)==pat.charAt(j))  
  21.                 {  
  22.                     next[++j]=++k;  
  23.                 }  
  24.                 else  
  25.                 {  
  26.                     next[++j]=0;  
  27.                 }  
  28.             }  
  29.             else  
  30.             {  
  31.                 if (k==-1 || pat.charAt(k)==pat.charAt(j))  
  32.                 {  
  33.                     next[++j]=++k;  
  34.                 }  
  35.                 else  
  36.                 {  
  37.                     k=next[k];  
  38.                 }  
  39.             }  
  40.        }  
  41.           
  42.         for (int s: next)  
  43.         {  
  44.             System.out.print(s+" ");  
  45.         }  
  46.         System.out.println();  
  47.     }  
  48. }

可以验证运行结果和代码一一致
进一步地，我们很容易就可以把代码三等价地改写成代码四：

代码四

  1. package nextcompute;  
  2. import java.util.*;  
  3.   
  4. public class nextcom4  
  5. {  
  6.     public static void main(String[] args)  
  7.     {  
  8.         String pat;  
  9.         Scanner input=new Scanner(System.in);  
  10.         System.out.println("请输入模式串");  
  11.         pat=input.nextLine();  
  12.           
  13.         int[] next=new int[pat.length()];  
  14.         int j, k;  
  15.         next[0]=-1; j=0; k=-1;  
  16.           
  17.         while (j<pat.length()-1)  
  18.         {  
  19.             if (k==-1 || pat.charAt(k)==pat.charAt(j))  
  20.             {  
  21.                 next[++j]=++k;  
  22.             }  
  23.             else  
  24.             {  
  25.                 if (k==0)  
  26.                     next[++j]=0;  
  27.                 else  
  28.                     k=next[k];  
  29.             }  
  30.         }  
  31.           
  32.         for (int s: next)  
  33.         {  
  34.             System.out.print(s+" ");  
  35.         }  
  36.         System.out.println();  
  37.     }  
  38. }

运行结果仍然和代码一相同。代码四形式非常简洁，但是仍然可以继续化简，注意到代码四第25行k==0为真时完全可以继续执行k=next[k],最后会在21行执行next[++j]==0,效果和第25行为真时执行next[++j]=0完全相同，故25-28行可统一写为k=next[k],从而得到形式最为简洁的代码五

  1. package nextcompute;  
  2. import java.util.*;  
  3.   
  4. public class nextcom4  
  5. {  
  6.     public static void main(String[] args)  
  7.     {  
  8.         String pat;  
  9.         Scanner input=new Scanner(System.in);  
  10.         System.out.println("请输入模式串");  
  11.         pat=input.nextLine();  
  12.           
  13.         int[] next=new int[pat.length()];  
  14.         int j, k;  
  15.         next[0]=-1; j=0; k=-1;  
  16.           
  17.         while (j<pat.length()-1)  
  18.         {  
  19.             if (k==-1 || pat.charAt(k)==pat.charAt(j))  
  20.             {  
  21.                 next[++j]=++k;  
  22.             }  
  23.             else  
  24.             {  
  25.                 k=next[k];  
  26.             }  
  27.         }  
  28.           
  29.         for (int s: next)  
  30.         {  
  31.             System.out.print(s+" ");  
  32.         }  
  33.         System.out.println();  
  34.     }  
  35. }

这(代码五)就是数据结构教科书上给出的next数组计算的代码实现，这样通过层层分析我们就确定了next数组计算代码的最简形式，也就是在各类文献资料书籍中最常见的形式。
字符串模式匹配的KMP算法中next数组计算方法的详细分析到此结束，笔者水平有限，若有错误和纰漏恳请指正，谢谢。

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/正经夜光杯/article/detail/847754
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号