串的匹配之KMP

KMP： D. E. Knuth, J. H. Morris, V. R. Pratt

本文复习KMP算法。它基于一个事实：从串S中寻找串P，当\(P_j\)与\(S_i\)作比较而不相等的时候，若此时需要\(S_i\)和\(P_k\)作比较，那么就会有：

\[P_1P_2...P_{k-1}=S_{i-k+1}S_{i-k+2}...S_{i-1} \]

容易看出，这是利用了上次的部分匹配结果。因为上次匹配结束时“\(P_j\)与\(S_i\)作比较而不相等”，所以又有：

\[P_{j-k+1}P_{j-k+2}...P_{j-1}=S_{i-k+1}S_{i-k+2}...S_{i-1} \]

将这两个式子结合，得到：

\[P_1P_2...P_{k-1}=P_{j-k+1}P_{j-k+2}...P_{j-1} \]

可见，模式串P上的迭代器的行为只和P自身有关。如果能事先计算出P串上迭代器的具体行为，就可以在主串迭代器不回溯的情况下快速完成串匹配。这就克服了传统匹配方法中S串迭代器需要不断回溯这一缺陷。根据上面的内容可知：一、粗略来说，\(k=f(j)\)，k、j满足上面式子。二、\(j=0\)时k不存在，因为此时不需要再和P串中的任何内容比较了，可以记作：\(f(0)=-1\)。三、为了充分利用上次的部分匹配结果，k值通常取所有满足上式的值中最大的那个。换句话说，对于某个j来说没有更大的k值能满足上式。这样，k和j的关系就明确了。如何计算出这些k值呢？书上用的是递推方法，原理自行理解，暂不详述。下面的代码可能有助于理解其计算规则：

int index_kmp(char* source, int slen, char* target, int tlen)
{
  int i, j;
  i = 0;
  j = 0;
  while(i < slen && j < tlen) {
    if(j == -1 || source[i] == target[j])
      ++i, ++j;
    else
      j = next[j];
  }
  if(j == tlen)
    return i - tlen;
  return -1;
}
void get_next(char* target, int tlen, int* next)
{
  int i, j;
  i = 0;
  j = -1;
  next[0] = -1;
  while(i < tlen - 1) {
    if(j == -1 || target[i] == target[j]) {
      ++i, ++j;
      next[i] = (T[i] != T[j]) ? j : next[j];  // 对于类似“aaaaaaaab”的模式串实施修正
    }
    else
      j = next[j];
  }
}

虽然KMP复杂度是\(O(m+n)\)，但是原始\(O(m*n)\)算法的表现在多数情况下并不是那么的不堪，反倒是KMP算法仅在模式与主串之间有很多“部分匹配”的情况下才显得快很多。