0

ここで Rabin-Karp アルゴリズムを理解しようとしていました: http://algs4.cs.princeton.edu/53substring/RabinKarp.java.html。

さまざまな記事を調べたところ、多項式ハッシュの一般的な形式は C1*A^k-1+C2*A^k-2+C3*A^k-3 であることがわかりました。コードを見ると、文字列の数字をどのように加算および減算するかがわかりました。

txtHash = (txtHash + Q - RM*txt.charAt(i-M) % Q) % Q; txtHash = (txtHash*R + txt.charAt(i)) % Q;

ここで、プログラムは先頭の数字を減算し、ハッシュ全体を乗算してから、新しい数字を追加しています。しかし、ハッシュを計算する関数を調べたところ、多項式ハッシュの一般的な形式に従っていませんでした。次のように見えました。

 private long hash(String key, int M) { 
    long h = 0; 
    for (int j = 0; j < M; j++) 
        h = (R * h + key.charAt(j)) % Q; 
    return h; 
}

この関数では、ハッシュと基数を乗算してから、key.charAt() を追加しています。関数が key.charAt() に R^k-1 から始まるベースを掛けていると思います。次に、for ループが続くと、基数が R で除算され、多項式の累乗が減少します。この関数がどのように機能し、上記の形式でハッシュをどのように生成するかを誰か説明してもらえますか? ありがとう！

4

1 に答える 1