KarpRabin模式匹配算法的朴素实现

Question

我在实现Karp-Rabin模式marcher的幼稚版本时遇到问题；我没有得到预期的结果。这是我的例子

string='today is a good day'
sub='good'

我想在上面的字符串中找到好的模式。你知道吗

def kapr(n,m):
    for i in range(len(n)-len(m)+1):
        for j in range(len(m)):
            if n[i+j-1]!=m[j]:
                continue
        return i
    return not found

Print (kapr(string, sub)) 

输出=0 预期的输出=11，应该与字符串中good的偏移量相对应。你知道吗

谢谢你的帮助。你知道吗

Answer 1

你想要break而不是continue。Continue将继续进行内部循环的下一次迭代，而break将退出内部循环。此外，使用break并不是直接跳转到外循环的下一个迭代，因此将使用return i语句。要阻止这种情况发生，可以使用for/else分支。你知道吗

例如

for j in range(len(m)):
    if n[i+j-1]!=m[j]:
        break
else:
    return i

只有内环正常完成时，它才会return i。你知道吗

它返回的索引也不是零索引，因此经过上述修改后，它将返回12。如果你想它是零索引，应该很容易更新！你知道吗