求解kmp算法next数组计算原理

本人原创，串的模式匹配——循序渐进，图文并茂，深入浅出——看了你就懂了。希望对你有所帮助。（贴图麻烦，请下载后查看。2 点财富值，物有所值。）

串的模式匹配

在主串中寻找与给定的模式串相等的子串（首次）出现的位置，即子串的定位操作，通常称作串的模式匹配。例如：主串S=“THIS IS HIS BAG”，模式串T=“IS”。如果从主串S的开头开始定位模式串T，模式匹配的结果就是3，即Index(S, T)=3。通常，还可以指定一个在主串中查找的起始位置，使算法更加灵活。如：从主串S中第7个字符开始定位模式串T，结果就是10，即Index(S, T, 7)=10。一般地，用Index(S, T, pos)表示从主串S中第pos个字符开始查找模式串T出现的位置。

(1) 简单的模式匹配算法

一种简单的模式匹配算法思路是：从主串S的第pos个字符开始和模式串的第一个字符比较，若相等，则继续逐个比较后续字符；否则再从主串的下一个字符开始重新和模式串比较。依次类推，直到匹配成功或失败。算法比较主串和模式串中的字符S[i]和T[j]时，一旦两者不匹配（不相等）（如图（a）所示），主串要回溯到匹配开始时的下一个字符，而模式串则需要回溯到开头。而匹配成功时，模式串在主串中的位置是i-T[0] （如图（b）所示）。

算法实现如下： int Index ( SString S, SString T, int pos )
{
  i = pos; j = 1;
  while( i<=S[0] && j<=T[0] ) {
    if( S[i]==T[j] ) { ++i; ++j; }
    else{ i= i-j+2;  j = 1; }
  }
  if( j>T[0] )  return i-T[0];
  else  return0;
}

算法在匹配过程中失配时主串需要回溯到匹配开始的下一个字符，而模式串则回溯到开头。如果主串长度为n，模式串长度为m，则简单模式匹配算法的时间复杂度在最好情况下为O(n+m)，但最坏情况下却达到O(n*m)。例如：主串S=“aaaaaaaaab”，模式串T=“aaab”。模式匹配过程中需要反复回溯，最终比较的字符数达到7*4个，此时的时间复杂度即O(n*m)。在通常的实际应用中，这种最坏情况出现的可能性并不大，该算法的时间复杂度接近于O(n+m)。但如果经常出现这种最坏情况，就需要修改算法了。KMP算法就能使模式匹配的时间复杂度在最坏情况下也能达到O(n+m)。

(2) KMP算法

KMP算法是对简单模式匹配算法的改进，它可以保证在O(n+m)的时间内完成模式匹配。KMP算法的主要改进在于：在匹配过程中S[i]≠T[j]出现字符失配时，主串指针i不回溯，而是充分利用已经得到的“部分匹配”结果，将模式串指针j回溯到一个“恰当”的位置，然后继续进行比较。这个模式串回溯的“恰当”位置通常由失配函数next[j]来定义，而理解KMP算法的关键就是理解失配函数next[j]的含义。

为了进一步理解失配函数next[j]的含义，举例如下图（a）。当S[i]与T[j]失配时（这里j=8），显然，经过前面的比较，S[i]与T[j]前面j-1个字符的子串是相等的，即S[i-j+1..i-1]=T[1..j-1]=”abcdabc”。观察该子串不难发现，其开头k=3个字符的子串与其末尾k个字符的子串相等，都等于”abc”。这也意味着，主串S[i]前面的k个字符S[i-k..i-1]与模式串T开头的k个字符T[1..k]已经完全匹配。所以，接下来，主串不用回溯，只要让模式串回溯到T[k+1]的位置（即令j=k+1）继续比较就可以了。从失配函数的角度来看，这里就有next[j]=k+1，该例中即有next[8]=4。

根据前面对具体实例的分析，可以大致总结出失配函数next[j]的计算方法：观察模式串失配字符前面的子串T[1..j-1]，若发现其开头（从T[1]开始向后数）k个字符的子串与其末尾（从T[j-1]开始向前数）k个字符的子串相等，则有next[j]=k+1。需要说明的是，为了让模式串回溯后，已经匹配的子串尽可能长，这里的k应该尽可能大，但要小于子串T[1..j-1]的长度j-1。例如：若T[j]失配时T[1..j-1]=”aaaaa”，则应取k=4，从而得到next[j]=5。另外，这里k的最小值可以是0，即当在模式串T[1..j-1]中找不到开头k个字符和结尾k个字符相等时，可以认为k=0。例如：当T[j]失配时T[1..j-1]=”abcde”，此时在开头和结尾找不到相等的子串，可以认为k=0，于是next[j]=1。

例1：模式串T=“ababaaab”，则next[6]=______。

【解析】求模式串任意位置j对应的next[j]值的问题，可以采用观察法，即直接观察前面的子串T[1..j-1]，确定首、尾最长相等子串的长度k，即可得到next[j]=k+1。这里，求模式串T的next[6]，观察第6个字符前面的子串“ababa”，可以看出分别从开头和末尾最多取长度为k=3的子串使两者相等，都是“aba”，所以，next[6]=k+1=4。

根据以上分析，在KMP算法中，主串S[i]与模式串T[j]失配时，主串i不回溯，模式串j根据失配函数回溯到next[j]。在已经求得失配函数的情况下，只要在前面简单模式匹配算法的基础上稍加修改即可：     if ( S[i]==T[j] ) { ++i; ++j; }
    else j = next[j];   // 主串i不回溯，模式串j回溯到next[j]

但是，还要注意一点：我们约定next[1] = 0。当主串S[i]与模式串第一个字符T[1]比较失配时（如上图（b）所示），因为next[1]=0，执行j=next[j]就会使得j变成0。接下来，若拿T[0]与主串S[i]比较显然是错误的，这里的T[0]实际上是字符串的长度。实际上，若主串中S[i]与模式串第一个字符T[1]不相等，就没有必要回溯再继续比较了，此时主串位置i应当加1向后移动一个字符，再从模式串开头j=1开始继续比较（注意到此时j==0，只要让j加1就可以了）。

最终，KMP算法的实现如下： int Index_KMP ( SString S, SString T, int pos )
{
  i = pos; j = 1;
  while( i<=S[0] && j<=T[0] ) {
    if( j==0|| S[i]==T[j] ) { ++i; ++j; }
    elsej =next[j];
  }
  if( j>T[0] )  return i-T[0];
  else  return0;
}

KMP算法的时间复杂度是O(n+m)，而且只需对主串扫描一次，但在进行模式匹配之前需要先计算模式串的失配函数，而且需要额外的m个空间存储失配函数的结果。下面讨论求模式串失配函数的具体方法。

(3) 求next[]算法

求模式串失配函数next[]的过程与KMP算法类似，只是主串与模式串是相同的。

若匹配过程中遇到T[i]==T[j]，j<i，如下图所示，容易看出子串T[1..i]中开头j个字符的子串与末尾j个字符的子串相等，于是若T[i+1]失配时模式串应回溯至T[j+1]继续比较，即得到失配函数值next[i+1]=j+1。反之，若匹配过程中T[i]≠T[j]，则利用KMP算法，令j回溯至next[j]。

下面是求失配函数next[]的算法实现。注意算法开始时，要初始化next[1]=0。由于循环中访问的是next[i+1]，为防止下标越界，循环条件修改为i<T[0]（而不是i<=T[0]）。同时，语句next[i+1]=j+1在i和j都加1之后也简化成了next[i]=j。 int get_next ( SString T, int next[] )
{
  i = 1; j = 0; next[1] = 0;
  while( i<T[0] ) {
    if( j==0 || T[i]==T[j] ) { ++i; ++j; next[i] = j;}
    elsej = next[j];
  }
}

例2：模式串T=“ababaaab”的next函数值依次为______。

【解析】求给定模式串的所有next[]值，可以有两种方法。第一种方法是观察法，逐个求解next[]值，具体步骤不再赘述。这种方法在模式串较长的情况下比较繁琐，容易出错。

第二种方法是利用前面的get_next()算法进行计算。为了便于计算，下面将计算过程用图形表示（如下图（a））。图中向右的箭头表示“计算过程”，即算法中的“i加1、j加1然后令next[i]=j”，向左的箭头表示j的“回溯过程”，即算法中的“j=next[j]”。满足条件j==0或T[i]==T[j]时，执行“计算过程”，并用一个由next[i]指向next[i+1]的向右箭头表示；否则，执行“回溯过程”，用从当前next值（等于j）向左指向next[j]的箭头表示。

计算模式串T的next[]值的整个过程如下图（a）所示，最终得到结果为0、1、1、2、3、4、2、2。下图（b）则进一步说明了从next[3]到next[4]的计算过程中，主要变量i、j、T[i]和T[j]之间的关系。

实际计算过程中，只要画出表示“计算过程”和“回溯过程”的箭头连线，就能够完整地反映出get_next()算法的执行过程。这种计算next[]值的方法简便、直观，只要稍加练习，该方法应该不难掌握。

(4) 求next[]修正值算法

前面算法求得的失配函数next[]值在特定条件下还可以进一步改进，以减少不必要的回溯。在前面的算法中已经知道，若匹配过程中遇到T[i]==T[j]，可以得到next[i+1]=j+1，即T[i+1]失配时模式串应回溯至T[j+1]继续比较。进一步考虑，如果此时还有T[i+1]==T[j+1]，如下图中均为‘d’，那么T[i+1]失配时，模式串回溯到T[j+1]也必然失配，此时不妨直接回溯至next[j+1]效率更高。若仍然失配，还可以继续类推。

例如，对于模式串T=”aaaab”，失配函数值为{0，1，2，3，4}，其中next[3]==2，同时T[3]==T[2]==’a’，也就是说，如果T[3]失配（主串中对应字符不等于’a’）回溯到T[2]的话，结果一定还是失配，此时应继续回溯到next[2]==1。实际上T[1]==T[2]==T[3]==’a’，可以继续回溯到next[1]==0。最终修正的失配函数值为{0，0，0，0，4}。

求失配函数next[]修正值的算法实现如下： int get_nextval ( SString T, int nextval[] )
{
  i = 1; j = 0; nextval[1] = 0;
  while( i<T[0] ) {
    if( j==0 || T[i]==T[j] ) {
      ++i; ++j;
      if(T[i]!=T[j]) nextval[i] = j;
      elsenextval[i] = nextval[j];  // 修正失配函数
    }
    elsej = nextval[j];
  }
}