KMP算法——next数组的计算

简介

  KMP算法是一种改进的字符串匹配算法，由D.E.Knuth，J.H.Morris和V.R.Pratt提出的，因此人们称它为克努特-莫里斯-普拉特操作（简称KMP算法）。KMP算法的核心是利用匹配失败后的信息，尽量减少模式串与主串的匹配次数以达到快速匹配的目的。具体实现就是通过一个next()函数实现。

顺序串类型的定义

struct SeqString {            /* 顺序串的类型 */
     int MAXNUM;              /* 串允许的最大字符个数 */ 
     int n;                   /* 串的长度，n<=MAXNUM*/ 
     char *c;
     };
typedef struct SeqString *PSeqString;        

计算next数组的代码（改进后）

makeNext(PSeqString p.int *next)
{ int i = 0,k = -1;
  next[0] = -1;                   /* 初始化 */
  while(i<p->n-1){                /* 计算next[i+1] */
       while(k>=0 && p->c[i]!=p->c[k])
       k = next[k];
       i++;k++;
       if(p->c[i] == p->c[k])next[i] = next[k];
       /* 填写next[i]，同时考虑改善*/

       else next[i] = k;
       }
}

如何计算一个字符串的next数组

   上面的代码不理解暂时没关系，我们先来看一下如何在书面上计算一个给定字符串的next数组。
  给定一个字符串p=“abcaababc”，列表计算next数组如下图，其中k表示p0…pi-1中最大相同的前后缀长度k。

  具体计算步骤如图所示从上到下计算即可，其中最后一行的next[i]分为两种情况：

1. 如果pk≠pi，next[i]=k（即对应列的k值）；
2. 如果pk=pi，next[i]=next[k]；

  知道了如何列表计算next数组后，对于任何给定的字符串，我们都可以这样去计算next数组的值。这时我们再返回去看计算next数组的代码，应该能很容易理解了。