//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]))
  {
   j++;
   k++;
   next[j]=k;
  }
  else
   k=next[k];
}