KMP算法

//200624101101楊振平

#include <stdio.h>

//全局變量計算比較次數

int count=0;

void main()

{

 //聲明KMP算法的函數原型

 int KMP(char S[],int n,char T[],int m);

 //初始化主串

 char S[14]="ababcabcacbab";

 printf("主串：%s/n",S);

 //初始化子串

 char T[6]="abcac";

 printf("子串：%s/n",T);

 //輸出比對結果

 printf("串比對位置：%d/n",KMP(S,13,T,5));

 printf("串比對比較次數：%d/n",count);

}

//求KMP算法函數

int KMP(char S[],int n,char T[],int m)

 //聲明求next數組的函數原型

 void GetNext(char T[],int next[],int m);

 int next[13];

    GetNext(T,next,m);

 int i=0;

 int j=0;

 while(i<n && j<m)

 {

  if(S[i]==T[j] && ++count)

  {

   i++;

   j++;

  }

  else

   j=next[j];

   if(j==0)

   {

    i++;

    j++;

   }

 }

 if(j<=m)

  return i-j+1;

 else

  return 0;

//求next數組函數

void GetNext(char T[],int next[],int m)

 next[1]=0;

 int j=1;

 int k=0;

 while(j<m)

  if((k==0)||(T[j]==T[k]))

   k++;

   next[j]=k;

   k=next[k];