学步园

#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;  
}