需要澄清KMP算法的最佳时间复杂度和最差时间复杂度。让我感到困惑的是最差的搜索时间复杂度为 O(n)。网上看了一下明白是有两个索引。一个索引 i 用于文本，另一个索引 j 用于模式。并且我们不会递减文本索引 i。但当存在不匹配且 j 值大于 0 时，我们会递减模式索引 j。在这种情况下，i 保持不变。那么最坏时间复杂度怎么可能是O(n)呢？应该比 O(mn) 还要多。对于 i 的特定值，我们可以对 j 进行多次迭代。
最好的情况是什么？这与最坏的情况有什么不同吗？我正在寻找简单的解释，因为我已经完成了不同的教程。