暴力算法更实用：字符串匹配平均比较次数

摘要: 字符串匹配的暴力算法平均情况时间复杂度

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

---

在文章 KMP算法与代码模板 中，我们介绍了字符串精确匹配的 KMP 算法，这应该也是名声最大的算法，它是一种预处理+响应查询的思想，通过巧妙设计的预处理信息，避免扫描指针的回退，使得在最坏情况下也有线性的时间复杂度。

事实上，在实用场景中，字符串的精确匹配的暴力算法就很有效，原因在于如果输入数据分布是均匀的，暴力算法在平均情况下的时间复杂度依然是线性的。本文我们来推导一下这个事情。主要用到的数学知识是期望的线性性、几何级数以及不等式的放缩。

其中期望的线性性非常重要，在很多算法分析问题中需要用到，比如快速排序平均情况分析、哈希表的分析等，这里简单介绍一下，定理如下：

定理（期望的线性性）

对于任意一组有限个具有有限期望的离散随机变量 $X_{1},X_{2},\cdots,X_{n}$，有：

$$E[\sum\limits_{i=1}\limits^{n}X_{i}] = \sum\limits_{i=1}\limits^{n}E[X_{i}]$$

以上定理的证明可以参考 Mitzenmacher 的《概率与计算》第二章。本书非常精彩，力荐，可以从以下链接下载。

• 《概率与计算》

算法导论的一个题可以参考，即第三版的第 32 章的练习 32.1-3。解决该练习，自然也就得出了暴力算法的平均时间复杂度。

暴力算法

记主串为 T，模式串为 P。

暴力算法通过一个循环找到所有的有效匹配，该循环对 $n-m+1$ 个可能的匹配起点 $i$ 进行检测，看是否满足条件 P[0..m-1] = T[i..s+m-1]。完整算法如下：

n = len(T)
m = len(P)
for i = 0,1,...,n-m
    if P[0..m-1] = T[i..i+m-1]
        记录匹配成功

平均情况分析

以下为《算法导论》第三版中的习题。

题解

记主串 $T$ 中匹配模式串 $P$ 的起点为 $i$，这样如果 T[i..i+m-1] = P[0..m-1]，则匹配成功。匹配起点 $i$ 的所有可能取值为 $0,\cdots,n-m$。

对于起点为 $i$ 的这一轮匹配，P[j] 需要与 T[i+j] 对比的概率即为 T[i..i+j-1] = P[0..j-1] 相同的概率，即 $\frac{1}{d^{j}}$。这样该轮次匹配的比较次数期望为 $\sum\limits_{j=0}^{m-1}\frac{1}{d^{j}}$。

由期望的线性性（注意定理对独立性没有要求），对 $i=0,\cdots,n-m$ 的各次匹配的期望比较次数求和，可得总的期望比较次数为 $(n-m+1)\sum\limits_{j=0}^{m-1}\frac{1}{d^{j}}$，由几何级数和不等式的放缩，可做以下推导：

$$\begin{align} (n-m+1)\sum\limits_{j=0}^{m-1}\frac{1}{d^{j}} &= (n-m+1)\frac{1 - d^{-m}}{1 - d^{-1}} \\ &\leq (n-m+1)\frac{1}{1 - d^{-1}} \\ &\leq 2(n- m + 1) \end{align}$$

$\Box$

由以上习题的结论，我们可以知道，字符串匹配的暴力算法的时间复杂度为 $O(n - m)$，且没有预处理的额外开销，因此实际应用中暴力算法普遍优于 KMP 算法。

---