本文共 776 字，大约阅读时间需要 2 分钟。

BF算法最差情况下执行的次数为什么是（n-m+1）*m？

首先BF算法的思想就是将目标串S的第一个字符与模式串T的第一个字符进行匹配，若相等，则继续比较S的第二个字符和 T的第二个字符；若不相等，则比较S的第二个字符和T的第一个字符，依次比较下去，直到得出最后的匹配结果。

可以总结为从头到目标挨个遍历。

显而易见最差的情况就是除去结尾可以完全匹配，在移动的过程中每次都是最后一个出错。

比如有   1111，1110 要匹配的是1110 这个（中间的逗号是为了区分）。需要执行到逗号后的也就是第5位才能真正开始正确匹配。前面浪费的趟数就是（总长度减去目标长度），也就是（8-4）=5。每趟走目标字符串个长度。因此现在是 4*4=16，而正确匹配需要再加上正确的执行次数（目标串的长度）4，总结需要执行次数为16+4=20。符号化就是：n为源串总长度，m为目标串长度，最差情况下执行的次数为（n-m+1）*m。

KMP算法最差情况执行的次数是多少？

同样，先了解KMP算法：假设现在文本串S匹配到 i 位置，模式串P匹配到 j 位置。如果j = -1，或者当前字符匹配成功（即S[i] == P[j]），都令i++，j++，继续匹配下一个字符。如果j != -1，且当前字符匹配失败（即S[i] != P[j]），则令 i 不变，j = next[j]。此举意味着失配时，模式串P相对于文本串S向右移动了j - next [j] 位。换言之，当匹配失败时，模式串向右移动的位数为：失配字符所在位置 - 失配字符对应的next 值，即移动的实际位数为：j - next[j]，且此值大于等于1。

根据算数原理显而易见，KMP算法最差情况时，由于指针i不需要回溯，比较次数仅为n,即使加上计算next[j]时所用的比较次数m，比较总次数为n+m=O(n＋m)。

转载地址：http://rxtrn.baihongyu.com/