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

提到常见的字符串匹配算法，一般来说我们会想到一个是朴素算法（暴力破解），一个是比较巧妙的 KMP 算法。

KMP 算法图解

如果要在一个主串 ABCDABCDEF 里找关键字 ABCDABE，有哪些方法呢？我们很容易想到用暴力破解方法实现关键字搜索，如下图所示：

比较 i 指针和 j 指针指向的变量是否相同，如果相同，i 和 j 同时后移。

本文约定待查找的字符串为主串 master 用 M 表示，关键字就是需要匹配的模式 pattern，用 P 表示。

到上图发现 M[i]!=P[j]，于是 j 回到开头，将关键字右移一位，然后继续重复昨天的故事。

上述是最坏的情况，一直比较到最后一位才不匹配，这种最坏情况下时间复杂度是 M*N，或许有人会觉得就这么暴力破解也行，不会这么巧每次都要到最后几位才发现不匹配。

然而数据在计算机里都是以 0101 这种二进制形式存储的，比如字符 1 是 00110001，字符 2 是 00110010，很容易发生直到最后几个字符才出现不匹配的情况，所以对于这样低效的算法,我们是不能容忍的，因此有了本文接下来介绍的 KMP 算法。

当发现最后一个字符不匹配时，如果我们人为查找，不会重头一个一个匹配，而是会像下图这样查找，i 不动，j 移动到下图中位置。因为根据已经匹配的信息，我们知道 M 中指针 i 前面的两个 AB 和 P 中 j 前面的两个 AB 是相同的。

KMP 算法就是利用已经部分匹配这个有效信息，保持 i 指针不回溯，移动模式串的 j 指针到有效的位置。关键点在于当 pattern 中某个字符与主串不匹配时，j 指针要移动到哪？

由上图，我们可以发现，当匹配失败时，j 要移动的下一个位置 k。存在着这样的性质：pattern 中最前面的 k 个字符和 j 之前的最后 k 个字符是一样的。

即 P[0,k-1] == P[j-k,j-1]

那么到底为什么可以移动到 k 呢？可以证明：

当 M[i] != P[j]

已经有 M[i-j,i-1] == P[0,j-1]

又有 P[0,k-1] == P[j-k,j-1]

可得 M[i-k,i-1] == P[0,k-1]

所以我们可以直接从 P[k]开始比较。同时，我们还发现 k 是与主串无关的，只与 pattern 有关，看下图更明显。k 可以完全由 pattern 得到，k 只要满足 P[0,k-1] == P[j-k,j-1]即可。

那么我们完全可以根据 pattern 预处理生成一个 next 数组，next[j]的值（即 k）表示，当 P[j] != M[i]时，j 指针的下一步移动位置。

由下图可以发现一个规律，当 P[k]==P[j]时，next[j+1]==k+1。

那么当 P[k]!=P[j]时呢？

上图看不出规律，转换成下图这样就比较明朗了。

当就 j!=k 时，意味着没有 ABAEABAH 这样长的前缀，但我们可以退而求其次，在 ABAEABAH 中寻找最长的前缀。

则问题可以转化为在搜索 pattern ABAEABAH 时，H 和主串不一样了。 因此这时 k=next[k]，然后重复上述步骤，继续把现在的 P[k]和 P[j]比较。

走到上图发现现在的 P[k]和 P[j]还是不相等，则继续重复上述步骤，此时 k=next[next[k]]。

发现终于 P[k]==P[j]了，因此我们可以得到 next[j+1]==k+1（此时 k=next[next[next[j]]])。

总结一下：

比较 P[k]和 P[j]，当 P[k]！=P[j]时，令 k=next[k]，继续比较 P[k]和 P[j]，一直重复上述步骤，直到 P[k]==P[j]或者 k 不能再前移为止,则 next[j+1]==k+1

代码如下：

/* *  @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 引擎源码实现源码地址看这里。

在 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()，你值得拥有~

作者介绍：

作者八路（企业代号名），目前负责贝壳找房商业化方向的前端工作。

本文转载自公众号贝壳产品技术（ID：gh_9afeb423f390）。

原文链接：

https://mp.weixin.qq.com/s/eLtQABruL9-Aut5fXl5x-g