本文是結合劉大有主編《數據結構》所寫筆記，如果想學習kmp.推薦http://blog.csdn.net/china8848/archive/2008/04/29/2342243.aspx
下面的估計我都看不懂
#include<iostream>
#include<cstdlib>
#include<string>
using namespace std;
int f[100];
void createf(string pat)//find數組
{
 memset(f,0,sizeof(f));
 int m=pat.size();
 f[0]=-1;
 for(int j=1;j<m;j++)
 {
  int i=f[j-1];
  while(pat[j]!=pat[i+1]&&i>=0)//只要p[j]與p[i+1]不等，則遞推計算i
  i=f[i];
  if(pat[j]==pat[i+1])
  f[j]=i+1;
  else
  f[j]=-1;
 }
}
/*                        已知f[13]=6;acbacbcacbacb,求f[14]acbacbcacbacba則先判斷pat[6+1]是否等于pat[14]，不等
                                再判斷 i=f[6]acbacb=3;判斷pat[14]pat[3+1]相等，則i=3
                           可得f[j]=3+1;         

*/
int kmp(string pat,string str)//求pat在str中的第一個匹配的起點
{
 int p=0,s=0;
 createf(pat);
 int m=pat.size();
 int n=str.size();
 while(p<m&&s<n)
 {
  if(pat[p]==str[s])
  {
   p++;s++;
  }
  else
  {
  if(p==0)s++;
  else
  p=f[p-1]+1;//s無需變化,舉例，abababababba
/*                                                          |
                                                             s指向a
                                                     ababb
//                                                           |
//                                                           p指向b,s和p失配

                                                    abababababba
//                                                          |
                                                            s  s不變
  由于ab=ab，既f[p-1]=2               ababb
//     p=f[p-1]+1=3                                |
//                                                          p  回到f[p-1]+1的位置;


相等，則s和p都加1.
//
*/
}
 }
     if(p<m)
     return -1;
     return s-m;
}