KMP算法实现

#include <iostream>  using namespace std;    /** * paramter pat:待匹配的字符串 * T: 返回的table * **/  void kmp_table(const char * W, int T[])  {      int pos = 2;  //当前查找的位置      int cnd = 0; //当前查找的前缀字串的位置          T[0] = -1;      T[1] = 0;        while(pos < strlen(W))      {          if( W[cnd] == W[pos-1] )           {              T[pos] = cnd + 1;              pos++;              cnd++;          }          else if( cnd > 0 )              cnd = T[cnd]; //回退，有难度            else           {              T[pos] = 0;              ++pos;          }      }    }    int kmp_search(const char * S,const char * W)  {      int m = 0 ; //开始匹配的位置      int i = 0 ; //W中位置        int * T = new int[strlen(W)];            kmp_table(W,T);        for(int j = 0; j < strlen(W); j++)      {          cout << T[j] <<" ";      }      cout<<endl;        while( (m + i) < strlen(S))      {          if(S[m+i] == W[i])          {              ++i;              if(i == strlen(W))                  return m;          }          else           {              m = m + i - T[i];              if( i > 0)  i = T[i];          }      }  }    int main()  {      char * S = "acabaabaabcacaabc";      char * W = "abaabcac";        int p = kmp_search(S,W);        cout<<"p = "<< p <<endl;  }