1

karp-rabin 部分文字列マッチング アルゴリズムを実装しています。私の実装は、部分文字列に対して hash_string() メソッドを呼び出すと正常に動作しますが、ローリング ハッシュを実装すると失敗します。ローリング ハッシュ値が増え続けていますが、その理由がわかりません。

def hash_string(string, base):
    power = len(string) - 1
    hash_value = 0
    for i in range(power, -1, -1):
        hash_value += (ord(string[i]) * (base ** power))
    return hash_value

def karp_rabin(string, substring):
    substrhash = hash_string(substring, 256)
    rolling_hash_val = hash_string(string[0:len(substring)], 256)
    for i in range(len(string) - len(substring) + 1):
        if substrhash == rolling_hash_val and string[i:i+len(substring)] == substring:
            return i
        if i < len(string) - len(substring):
            print rolling_hash_val
            print (ord(string[i]) * (256 ** (len(substring) - 1))) * 256
            rolling_hash_val = (rolling_hash_val - (ord(string[i]) * (256 ** (len(substring) - 1)))) * 256 + ord(string[i + len(substring)])

print karp_rabin('ababababaababab', 'aab')

より具体的には、ここで問題が発生します。

rolling_hash_val = (rolling_hash_val - (ord(string[i]) * (256 ** (len(substring) - 1)))) * 256 + ord(string[i + len(substring)])

部分文字列の長さが同じままであっても、ローリング ハッシュ値は桁違いに増加します。このローリング ハッシュの実装は正しいですか?

4

1 に答える 1

0

ローリング ハッシュは通常、モジュロ演算で行われます。つまり、そこにはあらゆる種類の足し算、掛け算、べき乗が行われています。モジュロでない場合n(一部の場合n)、はい、物事は成長します。

(ちなみに、ハッシュの更新に続いてモジュラスを実行することに誘惑されないでください。通常のサイズの整数では、それは良い考えではありません。実際の剰余累乗を使用してください。)

于 2015-09-18T20:41:02.280 に答える