模式匹配的KMP算法详解

模式匹配的KMP算法详解

这种由D.E.Knuth,J.H.Morris和V.R.Pratt同时发现的改进的模式匹配算法简称为KMP算法。大概学过信息学的都知道，是个比较难理解的算法，今天特把它搞个彻彻底底明明白白。

注意到这是一个改进的算法，所以有必要把原来的模式匹配算法拿出来，其实理解的关键就在这里，一般的匹配算法：

int Index(String S,String T,int pos)//参考《数据结构》中的程序
{
  i=pos;j=1;//这里的串的第1个元素下标是1
  while(i<=S.Length && j<=T.Length)
  {
    if(S[i]==T[j]){++i;++j;}
    else{i=i-j+2;j=1;}//**************(1)
  }
  if(j>T.Length) return i-T.Length;//匹配成功
  else return 0;
}

匹配的过程非常清晰，关键是当‘失配’的时候程序是如何处理的？回溯，没错，注意到(1)句，为什么要回溯，看下面的例子：

S:aaaaabababcaaa  T:ababc

aaaaabababcaaa
    ababc.(.表示前一个已经失配)
回溯的结果就是
aaaaabababcaaa
     a.(babc)
如果不回溯就是
aaaaabababcaaa
        aba.bc
这样就漏了一个可能匹配成功的情况
aaaaabababcaaa
      ababc

为什么会发生这样的情况？这是由T串本身的性质决定的，是因为T串本身有前后'部分匹配'的性质。如果T为abcdef这样的，大没有回溯的必要。

改进的地方也就是这里，我们从T串本身出发，事先就找准了T自身前后部分匹配的位置，那就可以改进算法。

如果不用回溯，那T串下一个位置从哪里开始呢？

还是上面那个例子，T为ababc，如果c失配，那就可以往前移到aba最后一个a的位置，像这样：
...ababd...
   ababc
   ->ababc

这样i不用回溯，j跳到前2个位置，继续匹配的过程，这就是KMP算法所在。这个当T[j]失配后，j应该往前跳的值就是j的next值，它是由T串本身固有决定的，与S串无关。

OK，了解到这里，就看清了KMP的大部分内容，然后关键的问题是如何求next值？先不管它，先看如何用它来进行匹配操作，也就是说先假设已经有了next值。

将最前面的程序改写成：

int Index_KMP(String S,String T,int pos)
{
  i=pos;j=1;//这里的串的第1个元素下标是1
  while(i<=S.Length && j<=T.Length)
  {
    if(j==0 || S[i]==T[j]){++i;++j;} //注意到这里的j==0,和++j的作用就知道为什么规定next[1]=0的好处了
    else j=next[j];//i不变（不回溯）,j跳动
  }
  if(j>T.Length) return i-T.Length;//匹配成功
  else return 0;
}

OK,是不是非常简单？还有更简单的，求next值，这也是整个算法成功的关键，从next值的定义来求太恐怖了，怎么求？前面说过了，next值表达的就是T串的自身部分匹配的性质，那么，我只要将T串和T串自身来一次匹配就可以求出来了，这里的匹配过程不是从头一个一个匹配，而是从T[1]和T[2]开始匹配，给出算法如下：

void get_next(String T,int &next[])
{
  i=1;j=0;next[1]=0;
  while(i<=T.Length)
  {
    if(j==0 || T[i]==T[j]){++i;++j; next[i]=j;/**********(2)*/}
    else j=next[j];
  }
}

看这个函数是不是非常像KMP匹配的函数，没错，它就是这么干的！注意到(2)语句逻辑覆盖的时候是T[i]==T[j]以及i前面的、j前面的都匹配的情况下，于是先自增，然后记下来next[i]=j，这样每当i有自增就会求得一个next[i]，而j一定会小于等于i，于是对于已经求出来的next，可以继续求后面的next，而next[1]=0是已知，所以整个就这样递推的求出来了，方法非常巧妙。

这样的改进已经是很不错了，但算法还可以改进，注意到下面的匹配情况：

...aaac...
   aaaa.
T串中的'a'和S串中的'c'失配，而'a'的next值指的还是'a'，那同样的比较还是会失配，而这样的比较是多余的，如果我事先知道，当T[i]==T[j]，那next[i]就设为next[j]，在求next值的时候就已经比较了，这样就可以去掉这样的多余的比较。于是稍加改进得到：

void get_nextval(String T,int &next[])
{
  i=1;j=0;next[1]=0;
  while(i<=T.Length)
  {
    if(j==0 || T[i]==T[j])
    { ++i;++j;
      if(T[i]!=T[j]) next[i]=j;
      else next[i]=next[j];//消去多余的可能的比较,next再向前跳
    }
    else j=next[j];
  }
}

匹配算法不变。

3、Next特征数组构造
    模式串P开头的任意个字符，把它称为前缀子串，如p0p1p2…pm-1。在P的第i位置的左边，取出k个字符，称为i位置的左子串，即pi-k+1... pi-2 pi-1 pi。求出最长的（最大的k）使得前缀子串与左子串相匹配称为，在第i位的最长前缀串。第i位的最长前缀串的长度k就是模板串P在位置i上的特征数n[i]特征数组成的向量称为该模式串的特征向量。
   可以证明对于任意的模式串p=p0p1…pm-1,确实存在一个由模式串本身唯一确定的与目标串无关的数组next，计算方法为：
   (1)  求p0…pi-1中最大相同的前缀和后缀的长度k;
   (2)  next[i] = k;

   作为特殊情况，当i=0时，令next[i] = -1;显然，对于任意i(0≤i   (1) n[0] ＝ -1，对于i > 0的n[i] ，假定已知前一位置的特征数 n[i-1]＝ k ；
   (2) 如果pi ＝ pk ，则n[i] ＝ k＋1 ；
   (3) 当pi ≠ pk 且k≠0时，则令k ＝ n [k -1] ; 让(3)循环直到条件不满足；
   (4) 当qi ≠ qk 且k ＝ 0时，则ni ＝ 0;

   根据以上分析，可以得到Next特征数组的计算方法，算法代码如下：

void get_next(SString T, int &next[])  
{  
    //求模式串T的next函数值并存入数组next  
    i = 1; next[1] = 0; j = 0;  
    while (i < T[0])  
    {  
        if(j ==0 || T[i] == T[j])  
        {  
            ++i; ++j; next[i] = j;  
        }   
        else   
        {  
            j = next[j];  
        }     
    }  
} 
void get_next(SString T, int &next[])
{
 //求模式串T的next函数值并存入数组next
 i = 1; next[1] = 0; j = 0;
 while (i < T[0])
 {
  if(j ==0 || T[i] == T[j])
  {
   ++i; ++j; next[i] = j;
  }
  else
  {
   j = next[j];
  } 
 }
}

   文献[5]中解释了以上计算方法存在一定缺陷，存在多比较的情况，可对其进行修正，得到如下算法：

view plaincopy to clipboardprint?
void get_next(SString T, int &next[])  
{  
    //求模式串T的next函数值并存入数组next  
    i = 1; next[1] = 0; j = 0;  
    while (i < T[0])  
    {  
        if(j ==0 || T[i] == T[j])  
        {  
            ++i; ++j;  
            if (T[i] != T[j])  
                next[i] = j;  
            else 
                next[i] = next[j];  
        }   
        else   
        {  
            j = next[j];  
        }     
    }  
} 
void get_next(SString T, int &next[])
{
 //求模式串T的next函数值并存入数组next
 i = 1; next[1] = 0; j = 0;
 while (i < T[0])
 {
  if(j ==0 || T[i] == T[j])
  {
   ++i; ++j;
   if (T[i] != T[j])
    next[i] = j;
   else
    next[i] = next[j];
  }
  else
  {
   j = next[j];
  } 
 }
}

   4、算法实现
   KMP算法的难点就是有限自动机的构造和特征向量的计算。解决了这两个问题后，具体匹配算法就很简单了。

   int   Index_KMP(SString   S,SString   T,int   pos){ 
              //利用模式串T的next函数求T在主串S中第pos个字符之后的位置的KMP算法。 
              //其中，T非空，1≤pos≤StrLength(S)。 
              i=pos;   j=1; 
              while(i <= S[0] && j<= T[0]){ 
                      if(j == 0 || S[i] == T[j]) { ++i; ++j; }//继续比较后继字符 
                      else   j = next[j];//模式串象右移动 
              } 
              if(j>T[0])   return   i-T[0];//匹配成功 
              else   return   0; 
   }//Index_KMP