1

在最终了解了 KMP 算法之后，它的复杂性仍然不清楚。对于模式 M 的长度和文本 N 的长度，我知道，在最坏的情况下，它是 O(N+M) （仍然无法解释，为什么），但为什么平均是 O(N)案子？提前感谢您的帮助。

4

1 回答 1

0

在这个答案中，我将解决您问题的这一部分。

对于模式 M 的长度和文本 N 的长度，我知道，在最坏的情况下，它是 O(N+M) （仍然无法解释，为什么）

我将尝试解释为什么计算失败函数（KMP算法中的预处理步骤）需要线性时间，您可以对算法的字符串匹配部分的运行时间进行类似的分析。

代码（取自这里）：

KNUTH-MORRIS-PRATT 失败 (P)

Input : Pattern with N characters
Output: Failure function f for pattern P

i ← 1
matched ← 0
f(0) ← 0
while i < N do
 if P[matched] = P[i]
     f(i) ← j +1
     i ← i +1
     matched← matched + 1
 else if matched>0
     matched ← f(matched - 1)
 else
     f(i) ← 0
     i ← i +1

计算失败函数的运行时间=while循环的最大迭代次数。

while循环的迭代次数=成功匹配的次数+不成功的匹配次数

我们称此语句为 (1)

让 N = 模式的长度。

成功匹配数<=N
（例如，检查此模式“aaaa”）

我们称这个语句为 (2)

不成功匹配的数量有点棘手。

让我们以模式“aaabcaaabce”为例

对于这种模式，数组是：

| 0 | 1 | 2 | 0 | 0 | 1 | 2 | 3 | 4 | 5 | 0 |

请注意，在索引 3 中，当发生不匹配时，当我们下降到值 0 时，我们最多可以做 2 个不匹配，或者换句话说，我们只能做与到目前为止匹配的字符数一样多的不匹配。

因此，每次在索引 i 处发生不匹配时，该索引 i 处的最大不匹配数最多可以是迄今为止匹配的字符数（在索引 i-1 处）。

直观地说，在整个数组上匹配的字符数只是数组中非零的条目。因为非零条目意味着匹配。自从，

最大不成功匹配数 = 匹配字符数

=> 整个数组的最大不成功匹配数

= 数组中匹配的最大字符数

= 数组中非零的条目数

<= N

因此，数组上的最大不成功匹配数 <=N

我们称这个语句为 (3)

将（1）、（2）和（3）放在一起：

总运行时间=成功匹配的运行时间+不成功匹配的运行时间

运行时间 <= N+N

运行时间 <= 2*N

计算失败函数的运行时间 = O(N)

于 2016-02-05T05:09:00.087 回答