C說話中完成KMP算法的實例講授

C說話中完成KMP算法的實例講授。本站提示廣大學習愛好者：（C說話中完成KMP算法的實例講授）文章只能為提供參考，不一定能成為您想要的結果。以下是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 101


void 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 ,char *a, int lA,int la)/* EASY*/
{
   int i,j,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,A,a,lA,la);
  if ( -1 == k)
  printf("Not Soulation!!! ");
  else
  printf("%d ",k) ;
  system("pause");
  
  return 0 ;
}