蛮力字符串匹配概念

Question

我在书中看到了这个问题。它规定如下：

         Suppose we use brute-force string matching to search for a pattern of length     
         m in a string of length n. In which of these cases will the worst-case
         running time be MAXIMUM? (k>1 is 
         an integer constant.)

         A. m = n-k
         B. m = n/k
         C. m = (n)^(1/k)
         D. m = k

对我来说，这是没有任何意义的，如何才能确保我们从4种选择中得到的模式会给我们最坏的时间复杂性。由于k是常数，所以对于n和k的不同值，我们会得到不同长度的m，它对搜索算法的复杂度有什么影响？

PS:我将选择第四个选项，考虑到n非常大，k= 1。

但同样，对于这种情况，我也必须作出假设，而且这是一个错误的答案。

Answer 1

对于蛮力字符串搜索，必须执行的测试数量如下：

m(n-m)

也就是说，您需要在它可以从(n-m)开始的每个位置上测试m，而对m的每次测试都需要m个字符。

当梯度为零时，此函数处于最大值，因此，对于m，您可以得到：

n-2m=0

这是备选方案B。

Answer 2

最糟糕的运行时间的蛮力R(m,n) = (n - m + 1) * m。(这是O(mn)，但让我们暂时保持精确的数值)。

您需要选择这样的m，使上面的R(m,n)成为最大的，这将是您的答案。

• A. m = n - k; R = (k + 1) * (n - k) --即n乘以常数，即O(n) --不太坏.
• D. m = k; R = (n - k + 1) * k -相同的O(n).

所以答案必须是B，C。你能根据描述的想法找出哪一个吗？(提示:选项B将给出二次O(n^2)复杂度)