python - 作业 : Implementing the Z algorithm in python, 真的很慢，比单纯的字符串搜索还慢

Question

我必须实现 Z 算法并使用它来搜索目标文本中的特定模式。我已经实现了我认为正确的算法和使用它的搜索功能，但它真的很慢。对于字符串搜索的简单实现，我得到的时间始终低于 1.5 秒，而对于 z 字符串搜索，我得到的时间始终超过 3 秒(对于我最大的测试用例)，所以我一定是做错了什么。结果似乎是正确的，或者至少对于我们给出的少数测试用例而言是正确的。我咆哮中提到的功能的代码如下:

import sys
import time

# z algorithm a.k.a. the fundemental preprocessing algorithm
def z(P, start=1, max_box_size=sys.maxsize):
    n = len(P)
    boxes = [0] * n
    l = -1
    r = -1

    for k in range(start, n):
        if k > r:
            i = 0
            while k + i < n and P[i] == P[k + i] and i < max_box_size:
                i += 1
            boxes[k] = i
            if i:
                l = k
                r = k + i - 1
        else:
            kp = k - l
            Z_kp = boxes[kp]
            if Z_kp < r - k + 1:
                boxes[k] = Z_kp
            else:
                i = r + 1
                while i < n and P[i] == P[i - k] and i - k < max_box_size:
                    i += 1
                boxes[k] = i - k    
                l = k
                r = i - 1
    return boxes

# a simple string search
def naive_string_search(P, T):
    m = len(T)
    n = len(P)
    indices = []
    for i in range(m - n + 1):
        if P == T[i: i + n]:
            indices.append(i)
    return indices

# string search using the z algorithm.
# The pattern you're searching for is simply prepended to the target text
# and than the z algorithm is run on that concatenation
def z_string_search(P, T):
    PT = P + T
    n = len(P)
    boxes = z(PT, start=n, max_box_size=n)
    return list(map(lambda x: x[0]-n, filter(lambda x: x[1] >= n, enumerate(boxes))))

Answer 1

您对 z 函数 def z(..) 的实现在算法上和渐近上都是正确的。

它在最坏情况下具有 O(m + n) 时间复杂度，而朴素字符串搜索的实现在最坏情况下具有 O(m*n) 时间复杂度，所以我认为问题出在您的测试用例中。

例如，如果我们采用这个测试用例:

T = ['a'] * 1000000 
P = ['a'] * 1000

我们将得到 z 函数:

real    0m0.650s
user    0m0.606s
sys 0m0.036s

对于简单的字符串匹配:

real    0m8.235s
user    0m8.071s
sys 0m0.085s

PS:你应该明白，有很多测试用例在线性时间内也可以进行简单的字符串匹配，例如:

T = ['a'] * 1000000 
P = ['a'] * 1000000

因此，对于简单的字符串匹配来说，最坏的情况是函数应该应用模式并一次又一次地检查。但在这种情况下，由于输入的长度，它只会进行一次检查(它无法应用索引 1 中的模式，因此它不会继续)。