当前位置:   article > 正文

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

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

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

 注意初始条件

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

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

代码四

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

运行结果仍然和代码一相同。代码四形式非常简洁,但是仍然可以继续化简,注意到代码四第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. public class nextcom4
  4. {
  5. public static void main(String[] args)
  6. {
  7. String pat;
  8. Scanner input=new Scanner(System.in);
  9. System.out.println("请输入模式串");
  10. pat=input.nextLine();
  11. int[] next=new int[pat.length()];
  12. int j, k;
  13. next[0]=-1; j=0; k=-1;
  14. while (j<pat.length()-1)
  15. {
  16. if (k==-1 || pat.charAt(k)==pat.charAt(j))
  17. {
  18. next[++j]=++k;
  19. }
  20. else
  21. {
  22. k=next[k];
  23. }
  24. }
  25. for (int s: next)
  26. {
  27. System.out.print(s+" ");
  28. }
  29. System.out.println();
  30. }
  31. }

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

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

闽ICP备14008679号