kmp算法

根据以上分析，可以得到Next特征数组的计算方法，算法代码如下：

void get_next(SString T, int &next[])
{
    //求模式串T的next函数值并存入数组next
    i = 1; next[1] = 0; j = 0;
    while (i < T[0])
    {
        if(j ==0 || T[i] == T[j])
        {
            ++i; ++j; next[i] = j;
        }
        else
        {
            j = next[j];
        }
    }
}

void get_next(SString T, int &next[]) { //求模式串T的next函数值并存入数组next i = 1; next[1] = 0; j = 0; while (i < T[0]) { if(j ==0 || T[i] == T[j]) { ++i; ++j; next[i] = j; } else { j = next[j]; } } }

   文献[5]中解释了以上计算方法存在一定缺陷，存在多比较的情况，可对其进行修正，得到如下算法：

void get_next(SString T, int &next[])
{
    //求模式串T的next函数值并存入数组next
    i = 1; next[1] = 0; j = 0;
    while (i < T[0])
    {
        if(j ==0 || T[i] == T[j])
        {
            ++i; ++j;
            if (T[i] != T[j])
                next[i] = j;
            else
                next[i] = next[j];
        }
        else
        {
            j = next[j];
        }
    }
}

void get_next(SString T, int &next[]) { //求模式串T的next函数值并存入数组next i = 1; next[1] = 0; j = 0; while (i < T[0]) { if(j ==0 || T[i] == T[j]) { ++i; ++j; if (T[i] != T[j]) next[i] = j; else next[i] = next[j]; } else { j = next[j]; } } } 

   4、算法实现
   KMP算法的难点就是有限自动机的构造和特征向量的计算。解决了这两个问题后，具体匹配算法就很简单了。

   int   Index_KMP(SString   S,SString   T,int   pos){ 
              //利用模式串T的next函数求T在主串S中第pos个字符之后的位置的KMP算法。 
              //其中，T非空，1≤pos≤StrLength(S)。 
              i=pos;   j=1; 
              while(i <= S[0] && j<= T[0]){ 
                      if(j == 0 || S[i] == T[j]) { ++i; ++j; }//继续比较后继字符 
                      else   j = next[j];//模式串象右移动 
              } 
              if(j>T[0])   return   i-T[0];//匹配成功 
              else   return   0; 
   }//Index_KMP