常见字符串匹配算法以及 JS 的 Sring.prototype.indexOf() 源码分析

/* 
*  @brief 计算部分匹配表，即 next 数组.
*  @param[in] p 模式串 
*  @param[in] next 数组 
*  @return 无
*/ 
function compute_prefix (p, next) {
  next[0] = -1;  //注释1 
  let j = 0; 
  let k = -1; 
  while (j < p.length - 1) {
    if (k == -1 || p[j] == p[k]) {
      next[++j] = ++k; //注释2
    } else {
      k = next[k];
    }
  } 
}

代码注释:

• 注释1 当pattern第一位就不匹配时，j无法左移应保持不变，只需移动i，所以初始化next[0]=-1

• 注释2 如下图，当j=1时,只能移动到0位置。而进入循环前初始化k=-1,进入循环首先就计算next[1]的值，所以当k==-1时next[++j] = ++k

到现在，我们基本完成了生成预处理数组的任务，上面的代码看上去很不错了，然而它还有一个小缺陷。

如下图，当P[j]==P[k]时，之前的P[j]匹配不上，现在的P[k]肯定也匹配不上，所以这时的k要前移。

所以在P[j]==P[next[j]]的特殊情况下，我们需要小小地修改一下代码：

function compute_prefix (p, next) {
  next[0] = -1; let j = 0; let k = -1;
  while (j < p.length - 1) {
    if (k == -1 || p[j] == p[k]) {
      if (p[++j] == p[++k]) { 
        next[j] = next[k];
      } else {
        next[j] = k;
      }
    } else {
      k = next[k];
    }
  } 
}

完整的KMP算法如下：

/* 
*  @brief KMP算法
*  @param[in] P pattern模式串 
*  @param[in] M master主串 
*  @return 无
*/
function KMP (M, P) {
  let i = 0; // 主串的位置
  let j = 0; // 模式串的位置
  let next = [];
  compute_prefix (P, next);
  while (i < M.length && j < P.length) {
    if (j == -1 || M[i] == P[j]) { // 当j为-1时，要移动的是i，当然j也要归0
      i++;
      j++;
    } else {
      j = next[j]; // i不需要回溯了,j回到指定位置
    }
  }
  if (j == p.length) {
    return i - j;
  } else {
    return -1;
  }
}

看了上述KMP算法分析，各位童鞋是否觉得KMP在字符串搜索算法中算很不错的呢，我以前也这样以为，直到后来看到Boyer-Moore算法才发现，啊~当时我还太天真，Boyer-Moore算法平均要比KMP快3-5倍，在实际的工业生产中，比如GNU grep,还有各种文本编辑器的查找功能（Ctrl+F）大多用的BM（Boyer-Moore）算法。

KMP算法利用的是pattern的前缀，而Robert S. Boyer教授和J Strother Moore教授发明的BM算法利用的则是pattern的后缀，关于BM算法的介绍，限于篇幅，本文就不详细介绍了，推荐阮一峰老师的博文，里面对于BM算法有详细的介绍Boyer-Moore,基于BM算法还有Horspool算法，感兴趣的童鞋可以自行查阅资料。

下图是朴素算法，KMP算法，简化BM算法，BM算法，Horspool算法在不同长度的pattern下的性能比较。

由图我们可以清楚发现，当pattern长度越长，BM算法的表现越好，当长度大于7时，BM以及基于BM衍生出来的算法简直是一骑绝尘，把KMP狠甩在后面。

那么现在，在了解常用的字符串匹配算法后，我们一起来看看js中indexOf()是怎么实现的。

v8引擎源码实现 源码地址看这里。

（https://github.com/v8/v8/blob/master/src/string-search.h）

在src/string-search.h文件中一共定义了五种搜索算法：

1. SingleCharSearch

2. LinearSearch

3. InitialSearch

4. BoyerMooreHorspoolSearch

5. BoyerMooreSearch

具体使用哪种，是在初始化StringSearch时根据pattern长度定义的。

部分代码如下：

StringSearch(Isolate* isolate, Vector<const PatternChar> pattern)
      : isolate_(isolate),
        pattern_(pattern),
        start_(Max(0, pattern.length() - kBMMaxShift)) {
    if (sizeof(PatternChar) > sizeof(SubjectChar)) {
      if (!IsOneByteString(pattern_)) {
        strategy_ = &FailSearch;
        return;
      }
    }
    int pattern_length = pattern_.length();
    if (pattern_length < kBMMinPatternLength) {
      if (pattern_length == 1) {
        strategy_ = &SingleCharSearch;
        return;
      }
      strategy_ = &LinearSearch;
      return;
    }
    strategy_ = &InitialSearch;
  }

v8是c++实现的，不写c++的童鞋看着可能不太习惯，没关系，上面的代码总结一下就是下图（设pattern长度为length，其中kBMMinPatternLength在源码中设为7)。

可以看到indexOf()根据传入的pattern的长度选择对应长度下效率最高的匹配算法，真真是少林武功，集各家之所长啊~ 关于里面的每种算法，且待下回分解，总之一句话indexOf()，你值得拥有~