Karp-Rabinパターンマッチングアルゴリズムの無駄な実装

Question

パターンmarcherのナイーブバージョンKarp-Rabinの実装に問題があります。私は期待された結果を得ていない。ここに私の例があります。

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

の代わりに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を返します。インデックスをゼロにしたい場合は、更新する必要があります。