python - 强力字符串匹配算法的运行时

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 字符串匹配算法的最坏情况运行时间(也是 (nm))进行比较。我想我的困惑源于这样一个事实，即我的算法最初显示为 O(n) 运行时，因为它只是迭代输入 n，使用索引作为切片符号相等语句的输入？想法？

Answer 1

最坏的情况是 O(nm)，是的。因为，你看，== 测试测试每个字符串中的每个字符，这可能需要等同测试中最短字符串的长度。