string - 蛮力字符串匹配概念

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，我会选择第4个选项。

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

Answer 1

对于您的暴力字符串搜索，您必须执行的测试数量是:

m(n-m)

也就是说，您需要在每个可能从 (n-m) 开始的位置测试 m，并且对 m 的每个测试需要 m 个字符。

当梯度为零时，此函数处于最大值，因此，对 m 进行微分，您会得到:

n-2m=0

这是选项B。