学步园

假设在某一个时刻有如下的等式成立:str[0...k-1] = str[j - k...j - 1],那么next[j] = k,在这个前提下,继续进行下一个字符的匹配.
1)如果str[0...k] = str[j - k...j],那么next[j + 1] = next[j] + 1 = k + 1.
2)反之,如果上面的匹配不成立,那么就要从next[k]开始进行新的匹配,如果成功的话,那么:
next[j + 1] = next[next[j]] + 1 = next[k] + 1;
如果还是不能匹配成功就再从next[next[k]]的位置开始进行的新的匹配,直到匹配成功为止.如果这个过程一直进行下去都没有找到可以成功匹配的字符的话,那么next[j + 1] = 0,这时表示要从字符串的第一个位置开始新的匹配了.
用一个公式表示上述的算法,那么可以写作:
next[j] =
1)-1,当j = 0时;
2) Max{k | 0 <= k < j && str[0..k - 1] = str[j - k...j - 1]};
3)0,其他情况,此时匹配要从第一个位置重新开始.

所以求解next数组的算法如下：
void get_next(const string &s, int next[])
{
    int i,j=-1;
    next[0] = -1;                                  // 第一个字符的next值是-1,因为C中的数组是从0开始的
    for (i = 1; i< s.size();i++)
    {
       while(j!=-1&& s[j+1] != s[i])              // 如果匹配不成功且模式串游标还没有退回到第一个字符则j就回退到上一个next值
            j = next[j];
       if (s[j+1] == s[i])                        // 如果匹配成功则模式串游标向前走一步
            j++;
      next[i] = j;                                //存放当前的next值为此时模式串的游标值
    }
}

int KmpCompare(const string &s, const string &t,int pos)
{
    int i,j = -1;
    get_next(t,next);
    for (i = pos; i <s.size(); i++)
   {
     while (j!=-1&& t[j+1] != s[i])
           j = next[j];
      if (t[j+1] == s[i])
           j++;
     if (j == t.size()-1)                        //匹配成功
           return i-j;
   }
return -1;
}

转自http://hi.baidu.com/%8E%E1%D0%B3/blog/item/4a08010b6f47232f6b60fb2e.html