模式匹配算法KMP算法

一种改进后的模式匹配算法是(Knuth Morris Pratt)共同设计的,所以称之为 “KMP模式匹配算法”

KMP算法基本思想:
设s为目标串
设t为模式串
设i 和 j 分别指示目标串和模式串中待比较的字符位置,
开始时, 设 i=0 j =0;
如果s[i] = t[j] 则 i 和 j 的值分别增加1 ,反之i不变 j的值退回之 j=next[j]的位置
然后再对 s[i] t[j]进行比较,依次类推:
(1) j值退回到某个 j =next[j]时,有s[i] t[j] 则指针的值各增加1后,再继续匹配
(2) j值退回到 j = -1 ,此指令指针的值各增加1 即下一次对 s[i+1] 和 t[0]进行比较

KMP算法:

  #define MAXSTRLEN 256
  typedef struct
  {
    char ch_string[MAXSTRLEN];
    int len;
  }SString

 int Next[MAXSTRLEN];

 int KMPIndex(SString s,SString t)
 {
   int i,j,v;
   i = 0;
   j = 0;
  
   while(i < s.len && j < t.len)
   {
     if(j == -1 || s.ch_string[i] == t.ch_string[j]){
         i ++;
         j ++;
      }else
      {
       j = Next[j];
      }
   }
   
  if(j >= t.len)
     v = j-t.len;
  else
    v = -1;


  return v;


 }

从KMP算法中,Next数组关系着整个模式模式串匹配时的回退情况

例:
t = ‘aaab’;
当j =0 Next[j] =-1;
当j =1 Next[j] = 0;
当j =2 有 t[0]=[t1] =’a’ 所以 Next[j] =1 ;
当J=3 t[0]t[1] = t[1]t[2] =’aa’ 即 Next[j] =2;

getNext函数

#define MAXSTRLEN 256
typedef struct
{
  char ch_string[MAXSTRLEN];
  int len;
} 

int NEXT[MAXSTRLEN];

void getNext(SString s)
 {
   int i,k;
   k = -1;
   j = 0;
   Next[0] = -1;
   
   while(j < t.len -1)
   {
       if( k == -1 || t.ch_string[j] == t.ch_string[K])
        {
          j ++;
          k ++;
          Next[j]  = k;
        }else
         k = Next[k];
   }
 }

相关阅读:
模式匹配算法 BF