Z 函数计算 [已关闭]

问：

我正在尝试解决 Z 函数问题，但它在测试系统的最新测试中得到了错误的答案，时间为 0.549 毫秒，内存为 60.69 MB。

比较器是否正确？是否正确选择了变量 x 和 p 来计算哈希函数？

我比较的主要功能是：

x, p = 257, 10 ** 6 + 3 
...
def isequal(i, size): # i - index, size - length
    return (
            (h[i + size - 1] - h[i - 1] * x_pow[size]) % p ==
            h[size]
    )

我的算法使用前缀函数和二进制搜索：

x, p = 257, 10 ** 6 + 3 
h = [0] * n # Prefix function
x_pow = [0] * n # Array with powers x
x_pow[0] = 1

for i in range(1, n):
    h[i] = (h[i - 1] * x + ord(s[i])) % p
    x_pow[i] = (x_pow[i - 1] * x) % p

l, r = 0, n - i + 1
while r - l > 1:
    mid = (l + r) // 2
    if isequal(i, mid):
        l = mid
    else:
        r = mid
ans[i] = l

输入线路限制：1 <= 长度 <= 10 ^ 6。 字符串中的所有字符都是字母表的小写字母。 Z 函数的第一个元素是 0

完整代码：

s = ' ' + str(input())
n = len(s)
x, p = 257, 10 ** 6 + 3
h = [0] * n # Prefix function
x_pow = [0] * n # Array with powers x
x_pow[0] = 1

for i in range(1, n):
    h[i] = (h[i - 1] * x + ord(s[i])) % p
    x_pow[i] = (x_pow[i - 1] * x) % p


def isequal(i, size): # i - index, size - length
    return (
            (h[i + size - 1] - h[i - 1] * x_pow[size]) % p ==
            h[size]
    )

ans = [0] * n
for i in range(2, n):
    l, r = 0, n - i + 1
    while r - l > 1:
        mid = (l + r) // 2
        if isequal(i, mid):
            l = mid
        else:
            r = mid
    ans[i] = l

for x in ans[1:]:
    print(x, end = ' ')

它适用于我提供的所有测试（简单、复杂），所以我非常感谢任何帮助