Zobrist ハッシュ

値 $x$ ごとにランダムな整数 $h(x)$ を割り当て、集合のハッシュを $h(x)$ の XOR、多重集合のハッシュを $h(x)$ の和（ $2^{61} - 1$ で割った余り）で表します。異なる集合のハッシュが一致する確率は、1 回の比較でおよそ $2^{-61}$ です。

• ZobristHash(): 空の表で初期化
• get(x): 値 $x$ に割り当てた乱数（初めて使う値には新しく割り当てる）。 $O(1)$
• prefix_set(a): res[i] が $a_0, \ldots, a_{i-1}$ に現れる値の集合のハッシュになるリストを返す。 $O(N)$
• prefix_multiset(a): 累積和 res を返す。 $a_l, \ldots, a_{r-1}$ の多重集合のハッシュは (res[r] - res[l]) % MOD。 $O(N)$

比べたい列どうしには、同じ ZobristHash を使います。

例（ $a$ の先頭 $x$ 個と $b$ の先頭 $y$ 個で、現れる値の集合が等しいか）:

Z = ZobristHash()
ha, hb = Z.prefix_set(a), Z.prefix_set(b)
# ha[x] == hb[y] なら等しい

コード

from random import randrange

MOD = (1 << 61) - 1


class ZobristHash:
    def __init__(self):
        self.table = {}

    def get(self, x):
        # 値 x に割り当てた乱数（1 以上 MOD 未満）
        h = self.table.get(x)
        if h is None:
            h = self.table[x] = randrange(1, MOD)
        return h

    def prefix_set(self, a):
        # res[i] = a[:i] に現れる値の集合のハッシュ（XOR）
        res = [0] * (len(a) + 1)
        seen = set()
        h = 0
        for i, x in enumerate(a):
            if x not in seen:
                seen.add(x)
                h ^= self.get(x)
            res[i + 1] = h
        return res

    def prefix_multiset(self, a):
        # (res[r] - res[l]) % MOD が a[l:r] の多重集合のハッシュ
        res = [0] * (len(a) + 1)
        h = 0
        for i, x in enumerate(a):
            h = (h + self.get(x)) % MOD
            res[i + 1] = h
        return res