KMP算法（《算法导论》）

//  KMP.cpp : Defines the entry point for the console application.
//
// 《算法导论》569页。模式匹配在于计算前缀与后缀的匹配，只有这样，才能把
// 前缀移位到当初匹配的后缀。因为是在前缀和后缀匹配的情况下。
#include  " stdafx.h "
#include  < iostream >
#include  < string >
using  std:: string ;
using  std::cout;
using  std::endl;

int *  Compute_Prefix_Function( char *  P)
... {
    int m = strlen(P);//计算模式的长度
    int *V = new int[m];//申请空间
    memset(V, 0, m*sizeof(int));//初始化为0
    V[0] = 0;
    int k =0 ;
    for(int q = 2; q < m; q++)
    ...{   //V[k]实际上是指第k个字符的最长前缀和后缀相等.《算法导论》（图32—10 |图32-11）有详细说明.
        while((k > 0) && (P[k+1] != P[q]))//当第k+1个字符和第q个字符不相等，本质就是V[k+1]不存在前缀和后缀相等
            k = V[k];//循环搜索所有的V[k]值，直到找到一个P[k+1] ==P[q]的值为止。还存在k=0和p[0] ==p[q-1]的情况
        if(V[k] == P[q-1])
            k = k + 1;
        V[q-1] = k;
    }
    return V;
}
void  KMP_Matcher( char *  T,  char *  P)
... {
    int n = strlen(T);
    int m = strlen(P);
    int* V = Compute_Prefix_Function(P);
    int q = 0;
    for(int i = 1; i <=n; i++)
    ...{
        while(q > 0 && P[q] != T[i-1])
            q = V[q-1];
        if(P[q] == T[i-1])
            q = q + 1;
        if(q == m)
        ...{
        
          cout<<" Pattern occurs with shift  " <<i-m<<endl;
          q = V[q-1];
        }
        
    }
    
   delete []V;
}


int  main( int  argc,  char *  argv[])
... {   
    char m[] = "l111111112klajia211bcabd112";
    char n[] = "112";
    KMP_Matcher(m, n);
    return 0;
}