暴力字符串匹配算法的运行时间

Question

我写了一个简单快速（写起来快，但运行起来不一定快！）的字符串匹配算法，使用的是Python：

def bruteMatch(n,m):
    for i in range(0,len(n)-len(m)+1):
        if n[i:len(m)+i]==m:
            return(i)

这个算法的运行时间会是O(nm)吗？我是在和Horspool字符串匹配算法的最坏情况运行时间进行比较，Horspool算法的最坏情况也是(nm)。我想我困惑的地方在于，我的算法最开始看起来像是O(n)的运行时间，因为它只是遍历输入的n，用索引作为切片的等式判断的输入？你们怎么看？

Answer 1

1. def bruteMatch(n,m):
       for i in range(0,len(n)-len(m)+1):
           if n[i:len(m)+i]==m:
               return(i)
   

   for i in range(0,len(n)-len(m)+1) 这个循环会执行 len(n)-len(m)+1 次

2. if n[i:len(m)+i]==m 这个判断会把字符串 n 中从位置 i 开始到位置 len(m)+i 的部分和字符串 m 进行比较

示例 1

n = "Hello"
m = "Jello"
len(n)-len(m)+1 = 4-4+1 = 1

range(0,1)

i=0
if n[0:4+0] == m ~ n[0:4] == m[:] ~ "Hello" == "Jello"
FALSE

示例 2

n = "Hi"
m = "Jello"
len(n)-len(m)+1 = 2-4+1 = -1

range(0,-1) ~ *LOGICAL ERROR*

示例 3

n = "Hello"
m = "Hi"
len(n)-len(m)+1 = 4-2+1 = 3

range(0,3)

i=0
if n[0:2+0] == m ~ n[0:2] == m[:] ~ "He" == "Hi"
FALSE

i=1
if n[1:2+1] == m ~ n[0:3] == m[:] ~ "Hel" == "Hi"
FALSE

i=2
if n[2:2+2] == m ~ n[0:4] == m[:] ~ "Hell" == "Hi"
FALSE

总结

你的代码会对 n[0:z] 进行比较，其中 z 的范围是 (0, len(n)+1)，总共会执行 len(n)-len(m)+1 次：

If len(n) == len(m) then check n == m
Else if len(n) > len(n) then return check m is in [ n[0:len(m)], .., n[0:len(n)] ]
Else if len(n) < len(m) then Error: Invalid range

Answer 2

这确实需要 O(n*m) 的时间。你会循环 (n-m) 次，而字符串比较本身需要 (min(n,m)) 的时间。当 n 或 m 很小的时候，这样做还可以，但想象一下最糟糕的情况，假设 m=n/2：

在这种情况下，循环会执行 (n-n/2) 次，而比较需要 (n/2) 的时间，总共就需要 (O(n^2)) 的时间——这可就不太好了！

如果性能很重要，并且搜索的字符串很大，可以考虑使用基于哈希的算法，比如 Rabin–Karp。

希望这对你有帮助！

Answer 3

最糟糕的情况是 O(nm)，没错。因为你看，== 这个测试会检查每个字符串中的每个字符，这可能会花费和最短字符串长度一样长的时间来进行比较。