KMP算法

D.E.Knuth、J.H.Morris和V.R.Pratt，发表一个模式匹配算法，可以大大避免重复遍历的情况，我们把它称为KMP算法

一般匹配字符串时，我们从目标字符串str（假设长度为n）的第一个下标选取和ptr长度（长度为m）一样的子字符串进行比较，如果一样，就返回开始处的下标值，不一样，选取str下一个下标，同样选取长度为n的字符串进行比较，直到str的末尾（实际比较时，下标移动到n-m）。这样的时间复杂度是O(n*m)。

KMP算法：可以实现复杂度为O(m+n)

算法代码如下：

获得子串的nextval数组:

void get_nextval (String T, int *nextval) {

       int i, j;

       i=1;

       j=0;

       nextval[1]=0;

       while (i<T[0]) {/*此处T[0]表示子串的长度*/

             if(j == 0 || T[i] == T[j]) {/*T[i]表示后缀的单个字符,T[j]表示前缀的单个字符*/

                       ++i;

                       ++j;

                       if(T[i] != T[j])/*若当前字符与前缀字符不同*/

                                 nextval[i] = j;/*则当前的j为nextval在i位置的值*/              

                        else

                                  nextval[i] = nextval[j]; /* 如果与前缀字符相同，则将前缀字符的nextval值赋值给nextval在i位置的值*/

              }

              else

                       j = nextval[j];

           }

}

获得要匹配的子串在主串中的位置

/* 返回子串在主串中第pos个字符之后的位置。若不存在，则返回0*/

/*T非空，1<=pos<=StrLength(S)。*/

int Index_KMP(String S, String T, int pos) {

    int i = pos;/*i用于主串当前位置下标，若pos不为1，则从pos位置开始匹配*/

    int j= 1;/*j用于子串T中当前位置下标值*/

    int next[255];/*定义一next数组*/

    get_nextval(T, next);/*对子串作分析，得到next数组*/

    while( i <= S[0] && j <= T[0] )/*所i小于主串的长度且j小于子串的长度时，循环继续*/

    {

         if (j==0 || S[i] == T[j])/*j=0或两字母相等继续*/

        {

            ++i;

             ++j;

          }

           else{/*指针后退重新开始匹配*/

                  j = next[j];/*j退回合适的位置，i值不变*/

             }

        }

         if(j > T[0])

               return i-T[0];

          else

               return 0;

}