http://www.cnblogs.com/wangguchangqing/archive/2012/09/09/2677701.html

• KMP算法的实现

KMP算法的是对匹配的模式匹配算法的改进，在s[i]和p[j]匹配不成功时，不是对主串进行指针的回溯，而是在p[1,…,j-1]中，寻找一个p[k],

用s[i]和p[k]进行下一轮的匹配。其实现的最大问题就是如何的根据p[1,…,j-1]来求出p[k]。

在KMP算法的实现中，使用一个辅助数组next[],使用该数组保存p[j]匹配不成功时，要进行下一轮匹配的k的值.即是当s[i] 和 p[j]匹配不成功时，

用p[ next[j] ]来和s[i]进行下一轮匹配，k = next[j] .

对数组next[] 的求解，可以goolge到不少的方法，这里使用最简单的递推的方法：

首先假定next[0] = –1,那么当next[j] = k时，就有：p[0,…,j-1] == p[j-k+1,…,j-1]。

这时，若有p[k] = p[j] ，则p[0,….,k] = p[j-k+1,..,j-1,j]，从而就有next[j+1] = next[j] + 1 = k +1 .

若p[k] != p[j] ,可以看着模式串对自身进行匹配的问题，即当匹配失败的时候，k值如何确定，k = next [k] .

求数组next[ ]的实现如下：

/*    KMP进行模式匹配的辅助函数    模式串和主串匹配不成功时，下次和主串进行匹配的模式串的位置*/void continue_prefix_function(const char * p , int * next) {    int j ;    int k ;    next[0] = -1 ;    j = 0 ;    k = -1 ;    while(j < strlen(p) - 1) {        if( k == -1 || p[k] == p[j]) {            j ++ ;            k ++ ;            next[j] = k ;        }else {            k =next[k] ;        }    }}

知道了当模式串和主串匹配不成功时，下一个和主串匹配的字符在模式串中的位置，在朴素的模式匹配的基础上很容易的写出KMP算法的代码如下：

/*    运用KMP算法的字符串模式匹配    在主串和模式串匹配不成功时，不对主串指针进行回溯，    例如用next[j],来指定下一次和主串进行匹配的模式串的位置*/int match_kmp(const char * s ,const char * p,int pos) {    int next[11] ;    int i = pos ;    int j = 0 ;    continue_prefix_function(p,next) ;    while(s[i] != ‘\0‘ && p[j] != ‘\0‘) {        if(s[i] == p[j]) {            i ++ ;            j ++ ;        }else {            if(next[j] == -1) {                i ++ ;                j = 0 ;            }            else {                j = next[j] ;            }        }    }    if(p[j] == ‘\0‘)        return i - j ;    else        return -1 ;}

KMP模式匹配