python3如何找到字节串的最大前缀，它是anoth的子串

Question

我需要找到一个bytes对象s1的最大前缀（从开头开始的字节串），它是另一个bytes对象s2的子串，并返回以s2和length为单位的起始位置。在这种情况下，s2碰巧也与s1重叠。在

最佳结果是最长的前缀从最接近s2的结尾开始。在

我试着用字节.rfind方法如下。在

注意：这是试图在src中查找前面在src中存在的、从索引maxOffset开始的最大前缀maxOffset，该前缀位于index之前的最大maxOffset字节内。因此，s1是src[index:]，s2是src[index-maxOffset:index+maxLength-1]。maxLength是我感兴趣的前缀的最大长度。在

def crl(index, src, maxOffset, maxLength):
    """
    Returns starting position in source before index from where the max runlength is detected.
    """
    src_size = len(src)
    if index > src_size:
        return (-1, 0)
    if (index+maxLength) > src_size:
        maxLength = src_size - index
    startPos = max(0, index-maxOffset)
    endPos = index+maxLength-1
    l = maxLength

    while l>1:
        if src[index:index+l] in src[startPos:index+l-1]:
            p = src.rfind(src[index:index+l], startPos, index+l-1)
            return (p,l)
        l -= 1
    return (-1, 0)

由于之前的实现非常缓慢，我也尝试了如下代码

^{pr2}$

虽然第二次实施更快，但仍然非常缓慢，我认为效率低下。我怎样才能提高效率和运行速度？在

Answer 1

为第二个字符串生成suffix array，然后在该数组中搜索第一个字符串，选择最长公共前缀的最后一个索引

Answer 2

在我看来，你可以使用一个修改过的Knuth-Morris-Pratt字符串来搜索匹配子字符串的agorithm，只要它能够匹配，并提醒找到的最长匹配。在

我不确定是否存在反向工作而不是向前的好处，因为当您找到匹配项时，您需要继续搜索更长的匹配项（除非您匹配了整个字符串）。在