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

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）吗？我将它与horsool字符串匹配算法的最坏情况运行时进行比较，后者也是（nm）。我想我的困惑源于这样一个事实：我的算法最初看起来是O（n）运行时，因为它只是迭代输入n，使用索引作为切片表示法等式语句的输入？思想？在

Answer 1

最坏的情况是O（nm），是的。因为，==测试测试每个字符串中的每个字符，这可能与相等测试中最短字符串的长度一样长。在

Answer 2

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

1. for i in range(0,len(n)-len(m)+1)将循环len(n)-len(m)+1次

2. if n[i:len(m)+i]==m将nfrom i to len(m)+i中的所有字符与m

例1

^{pr2}$

例2

^{3}$

<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 3

这确实需要O（n*m）时间。运行循环（n-m）次，字符串比较本身需要（min（n，m））时间。当n或m都很小时，这是很好的，但是考虑最坏的情况，其中m=n/2：

循环执行（n n／2）次，比较需要（n／2）时间，总共（o（n ^ 2））时间不太好了！在

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

希望这有帮助！在