卡普拉宾模式匹配算法的朴素实施

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，应的良好的字符串中的偏移量相对应。

感谢您的帮助。

Answer 1

你想要break而不是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.如果您希望将其更改为零索引，则应该很容易更新！