卡普拉賓模式匹配算法的樸素實施

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.如果您希望將其更改爲零索引，則應該很容易更新！