KMP算法

           KMP算法

 算法实质是发现不匹配的位时，只移动模式串j，
 前缀函数par[k] 实际上是找出模式串P中从1--k位置上的一个位置q
 使par[1 q]为par[1 k]的最大前缀，
 par[k-q+1 k]为par[1 k]的最大后缀，
 而且需要满足一个条件，即par[1 q] == par[k-q+1 k]
 
 使用这个前缀数组，有一个好处，就是模式串P，不需要每次查找失败时，都从初始位置处开始重新匹配。
 若P[q+1] != T[i] ，则只需要重新使q = par[q]。因为模式串的最长后缀与最长的前缀相同，所以不需要从最开始的位置开始移动。
 只需要移动到par[q]处。 然后继续 P[q+1]与T[i]比较，不相等则重复此过程。
 
 很可能q移动到0处，仍然不相同。这时候外层查找串T下标i进行自增。然后重复之前的操作
     

二 前缀数组的求法

 另外一个问题就是par这个前缀数组如何确定
  实际上这是一个模式串P自身匹配的过程。复杂度为o(M)，从2----m，逐个确定 par[i]
 两者都有一个共同的特点。若当p[i] != p[q+1]时，需要迭代q  = par[q] ,直到q==0 或者得到p[q+1] != p[i]时为止。

每一次循环确定一个par[i].

代码如下：

#include <iostream>
#include <cstring>
  using namespace std ;
  int par[20] ; //作为前缀数组   
  
  void iniPar(char * P , int * par , int m)
  {
    //构造字符串的前缀，实质上是字符串P的自我匹配 
     par[1] = 0 ;
     int i , j , q = 0 ;
     
     for(i = 2 ; i < m ; i++)
      {
          while(q > 0 && P[i] != P[q + 1]) 
             q = par[q] ;
          if(P[i] == P[q + 1])
             q++ ;
             
          par[i] = q ;
             
      }   
  }
  
  
  int main()
  {
    char T[100] = "0bacbabababacaab" ;
    char P[20] = "0ababaca" ;
    int m = strlen(P) ;
    int n = strlen(T) ;
    int q = 0 ; //表示当前P串正在比较的位置 
    int i , j , k ;
    
    
    
    iniPar(P , par , m) ; //构造前缀数组，实际上是P串的自我匹配，比较和P与T串的匹配相似 
    
    for(i = 1 ; i < n ; i++)
    {
      while(q > 0 && P[q+1] != T[i]) q = par[q] ; //则把P串左移     
      if(P[q+1] == T[i]) //如果当前匹配的相等，则继续移动p串  
        q++ ;
      if(q == m - 1)
        {
          printf("%d\n" , i - (m - 1) + 1) ;
          q = par[q] ; //继续寻找下一个      
        }   
    }
    
    for(i = 1 ; i < m ;i++)
      printf("%d " , par[i]) ;
    
     system("pause") ;
     return 0 ;  
  }

posted on 2011-05-05 20:33 kahn 阅读(429) 评论(0)  编辑 收藏 引用 所属分类: 算法相关