C语言中实现KMP算法的实例讲解

概述一般的算法为什么这么低效呢？那是因为主串指针回溯情况过多:主串指针如果不回溯的话，速度就会加快，那我们就会想：

一般的算法为什么这么低效呢？那是因为主串指针回溯情况过多:
主串指针如果不回溯的话，速度就会加快，那我们就会想：
如何让主串指针不回溯？
KMP算法就是解决了这个问题，所以速度变得更快速了。
它是这样子的：
用一个数组：next[] 求得失配时的位置，然后保存下来。
要说清楚KMP算法，可以从朴素的模式匹配算法说起。 
朴素的模式匹配算法比较容易理解，其实现如下   

 int  Index(char  s[],char  p[],int  pos)  {    int  i,j,slen,plen;    i  =  pos;    j  =  0;    slen  =  strlen(s);    plen  =  strlen(p);    while((i  <  slen)  &&  (j  <  plen))    {     if((s[i]  ==  p[j]))     {      i++;      j++;     }     else     {      i  =  i-j+1;      j  =  0;       }    }    if(j  >=  plen)    {     return  (i-plen);    }    else    {     return  -1;    }   }  

  
可见，在朴素的模式匹配算法中，当模式中的p[j]与主串中的s[i]不匹配时，需要把主串的指针回溯到i-j+1的地方从新用s[i-j+1]跟p[0]进行匹配比较。KMP算法的想法是，能不能不回溯主串的指针呢？这种想法基于如下事实的：p[j]!=s[i]前，p[0]~p[j-1]跟s[i-j]~s[i-1]是匹配的（这里j>0，也就是说在不匹配前已经有匹配的字符了。否则如果j=0,则主串指针肯定不用回溯，直接向前变成i+1再跟p[0]比较就是了） 
  
p[j]!=s[i]前，p[0]~p[j-1]跟s[i-j]~s[i-1]是匹配的，这说明了什么呢？这说明可以通过分析模式的p[0]~p[j-1]来分析s[i-j]~s[i-1]。如果模式中存在p[0]~p[k-1]=p[j-k]~p[j-1](共k个匹配的字符,且k是满足这个关系的最大值）,则可以知道s[i-k]~s[j-1]跟[0]~p[k-1]是匹配的，那么，s[i]只需要跟p[k]进行比较就行了。而这个k是跟主串无关的，只需要分析模式串就可以求出来（这就是普通的教材中next[j]=k这个假设的由来,普通教材中总喜欢假设这个k值已经有了，如果你逻辑思维强还没有什么，不然或多或少会把你卡在这的）。亦即next[j]=k。 
  
如果上述的p[0]~p[k-1]=p[j-k]~p[j-1]串不存在会怎么样呢？这说明p[j]前的串中不存在p[0]...=...p[j-1]的情况，就连p[0]也不等于p[j-1],也就是说p[0]~p[j-1]中所有以p[j-1]为结尾的子串跟模式p都是失配的。基于上面p[0]~p[j-1]=s[i-j]~s[i-1]的事实，可以断定s[i-j]~s[i-1]中所有以s[i-1]结尾的子串跟模式p都是失配，这说明把主串的指针回溯到i-j+1～i-1都是没有必要的，既然没有必要回溯，而s[i]!=p[j]，则s[i只能跟p[0]进行比较匹配了。亦即next[j]=0。 
  
特殊情况下，j=0，即s[i]!=p[0]，这时不用再用s[i]来跟p中的其它字符比较了，变成用s[i+1]跟p[0]进行比较。为了统一，可以让next[0]=-1。在下一轮的比较中，判断到j=-1的情况时，让i=i+1,j=j+1,自然就形成s[i+1]跟p[0]比较的效果了。  
 
KMP算法实现示例

具体请看如下程序：

#include <stdio.h>#include <stdlib.h>#include <string.h>#define MAX 101voID get_next( int *next,char *a,int la) /*求NEXT[]的值*/{   int i=1,j=0 ;   next[1] = 0 ;      while ( i <= la) /*核心部分*/   {      if( a[i] == a[j] || j == 0 )      {        j ++ ;        i ++ ;        if( a[i] == a[j])        next[i] = next[j];        else        next[i] = j ;      }      else      j = next[j] ;   }}int str_kmp( int *next,char *A,int lA,int la)/* EASY*/{   int i,k ;   i = 1 ;   j = 1 ;   while ( i<=lA && j <= la )   {      if(A[i] == a[j] || j == 0 )      {          i ++ ;          j ++ ;      }      else      j = next[j] ;   }      if ( j> la)   return i-j+1 ;   else   return -1 ;}int main(voID){  int n,k;  int next[MAX]={0} ;  int lA=0,la =0 ;  char A[MAX],a[MAX] ;  scanf("%s %s",A,a) ;    lA = strlen(A);  la = strlen(a);  for(k=la-1; k>= 0 ;k --)  a[k+1] = a[k] ;  for(k=lA-1; k>= 0 ;k --)  A[k+1] = A[k] ;    get_next(next,a,la) ;  k = str_kmp(next,lA,la);  if ( -1 == k)  printf("Not Soulation!!! ");  else  printf("%d ",k) ;  system("pause");    return 0 ;}

总结

以上是内存溢出为你收集整理的C语言中实现KMP算法的实例讲解全部内容，希望文章能够帮你解决C语言中实现KMP算法的实例讲解所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。