暴力匹配是模式匹配的一种，还有一个有名的叫 KMP 匹配，KMP 匹配的时间复杂度很稳定，保持在 $\mathcal{O}(n+m)$，由于要开辟 next 数组，空间复杂度是 $\Omega(m)$。暴力匹配虽然理解起来最简单，但平均时间复杂度比较复杂。【注：我认为平均比较次数就是平均时间复杂度，当然可以换一个定义，那么结论可能会与本文不同】
这是一个经典的示例：
P = "Odyssey"
T = "A space Odyssey is not about the Odyssey"
一般情况下，约定子串 P 的长度为 m，文本串 T 的长度为 n。我们会发现 P 子串在 T 文本串中遍历了 n - m + 1 轮，而每轮可能需要对比 m 次。
现在，我们更进一步约定条件：
- 文本串 T 不短于子串 P，即 $n\geqslant m$
- T 和 P 中所有字符出现概率独立同分布，假设服从均匀分布
- 按照数学习惯，索引一律从 1 开始
根据以上约定，当子串 P 与文本串 T 比较到第 i 轮时，若匹配成功，则必有：
那么，对于第 i 轮的第 j 次比较，$P_j$ 与 $T_{i+j-1}$ 相同的概率显然是一个古典概型。不妨记任意字符 c 出现的概率为 $\Pr(c)$，由于均匀独立同分布，所以 $P_j$ 这个字符与 $T_{i+j-1}$ 这个字符相同的概率为：$\Pr(c)\times\Pr(c)\times\mbox{字符集总个数}=\Pr(c)$。
其中，$\Pr(c)$ 就等于字符集总个数的倒数，常数。$P_j=T_{i+j-1}$ 意味着前面的 $j-1$ 个字符都是比较成功的，其概率为 $\Pr^{j-1}(c)$，毕竟，前 $j-1$ 个字符中但凡有一个比较失败的，子串 $P$ 都会继续往前移动一个单位，进入新的一轮匹配。
如果某轮仅有 $j$ 次比较，则意味着前 $j-1$ 次比较都成功了，且当前第 $j$ 次比较失败了。毕竟，要是第 $j$ 次还比较成功了，那么意味这轮必定还有第 $j+1$ 次比较。
因此，每轮匹配的比较次数分布律如下：
则每轮比较次数的数学期望：
记 $S=\color{red}\displaystyle\sum_{j=1}^{m-1}j{\Pr}^{j-1}(c)$，把 S 看作等比数列求和，然后错位相减：
化简得到：
最后将 S 代入数学期望 E 可得：
每轮比较次数的数学期望是 E，一共有 n - m + 1 轮，因此，整个模式匹配下来的平均比较次数：
我记得《数据结构》课本上说平均时间复杂度是 $\mathcal{O}(nm)$，这是因为真实情况下，字符集中每个字符肯定不是服从独立均匀同分布，好比 26 个英文字母出现的概率都不同。所以这里计算的只是一个理想值，或者说最小值。