ハッシュ化

Error

シーケンスのハッシュを計算するだけでなく、その各プレフィックスに値を保存できます。これらは対応するプレフィックスと等しいシーケンスのハッシュ値になることに注意してください。

このような構造を使用すると、このシーケンスのサブセグメントのハッシュ値をすばやく計算できます (プレフィックスの合計と同様)。

サブセグメント [l;r] のハッシュを計算したい場合は、プレフィックス r のハッシュを取得し、プレフィックス l-1 のハッシュと p の r-l+1 乗を減算する必要があります。なぜそうなるのかは、プレフィックスに値を書き込んで何が起こるかを確認すると明らかになります。この写真を見て成功することを願っています
。


このようなアクションの結果として、元のシーケンスのサブセグメントのハッシュが得られます。さらに、このハッシュは、このサブセグメントに等しいシーケンスからのハッシュとみなした場合のハッシュと等しくなります (他の値と比較するために次数などの追加の変換は必要ありません)。

ここで明確にしておくべき点は次の 2 つです
。 1) r-l+1 乗の p を素早く乗算するには、p modulo mod のすべての可能なべき乗を事前に計算する必要があります。
2) すべての計算はモジュロモジュロで実行されるため、プレフィックス ハッシュを減算すると負の数が得られる可能性があることに注意してください。これを回避するには、減算する前に常に mod を追加します。また、乗算とすべての加算の後に剰余値を取得することを忘れないでください。

コードでは次のようになります。
  #include <bits/stdc++.h> 名前空間 std を使用します。 typedef 長い長いll; const int MAXN = 1000003; // ベースモジュールとハッシュモジュール ll p、mod; // プレフィックスハッシュと指数 p h[MAXN]、pows[MAXN]; // サブセグメント [l;r] のハッシュを計算します ll get_segment_hash(int l, int r) { return (h[r] + mod - h[l - 1] * pows[r - l + 1] % mod) % mod; } int main() { // どうにかして p と mod を取得します // 累乗 p を事前計算します pows[0] = 1; for (int i = 0; i < MAXN; i++) pows[i] = (pows[i - 1] * p) % mod; /// // 主な問題の解決策 /// 0 を返します。 }

文字列 A のハッシュが h_A に等しく、文字列 B のハッシュが h_B に等しい場合、文字列 AB のハッシュをすぐに計算できます。
h_AB = h_A * p^|B| + h_B   <- すべてを剰余として数えます
ここで |B| - 文字列 B の長さ。

シーケンスに加えて、セットをハッシュすることもできます。つまり、順序のないオブジェクトのセットです。次の計算式に従って計算されます
。 hash(A) = \(\sum_{a \in A} p^{ord(a)}\)   <- すべてを剰余として数えます
ord は、セットのオブジェクトに、考えられるすべてのオブジェクトの中の絶対的な序数を割り当てる関数です (たとえば、オブジェクトが自然数の場合は ord(x) = x、小文字のラテン文字の場合は ord(& #39;a' ;) = 1、ord('b') = 2 など)

つまり、オブジェクトごとに、このオブジェクトの数の基数乗に等しい値を関連付け、セット全体のハッシュを取得するためにこれらの値をすべて合計します。式から明らかなように、要素がセットに追加またはセットから削除された場合、ハッシュは簡単に再計算されます (必要な値を加算または減算するだけです)。同じロジックです。 単一の要素が追加または削除されるのではなく、他のセットが追加または削除される場合（ハッシュを加算または減算するだけです）。

すでに理解されているように、単一の要素はサイズ 1 のセットとみなされ、ハッシュを計算できます。そして、より大きなセットは単にそのような単一セットの結合であり、セットを結合することでハッシュを追加します。

実際、これは同じ多項式ハッシュですが、p^m  の係数の前に、次の値がありました。 n - m - 1 (n はシーケンスの長さ) のシーケンス要素の数です。これは、絶対序数が m に等しいセット内の要素の数です。

このようなハッシュでは、絶対順序数 m を持つ p 個のオブジェクトのセットが絶対順序数 m を持つ 1 つのオブジェクトのセットと同じハッシュを持つ状況を避けるために、十分に大きなベース (セットの最大サイズより大きい) を取るか、二重ハッシュを使用する必要があります。序数 m+1。
 

根付いたツリーを効率的にハッシュする方法もいくつかあります。
これらの方法の 1 つは次のように整理されます。
深さのトラバースの順序で頂点を再帰的に処理します。単一の頂点のハッシュが p に等しいと仮定します。子を持つ頂点の場合、最初にそれらのアルゴリズムを実行し、次に子を通じて現在のサブツリーのハッシュを計算します。これを行うには、子のサブツリーのハッシュを一連の数値とみなして、このシーケンスからハッシュを計算します。これは現在のサブツリーのハッシュになります。
子の順序が重要でない場合は、ハッシュを計算する前に、子のサブツリーからハッシュのシーケンスを並べ替え、並べ替えられたシーケンスからハッシュを計算します。

このようにして、ツリーの同型性をチェックできます。子のハッシュを順序なしでカウントするだけです (つまり、子のハッシュをソートするたびに)。そして、ルートのハッシュが一致する場合、ツリーは同型であり、一致しない場合は一致しません。

根のない木の場合、すべてが同様の方法で起こりますが、重心を根と見なす必要があります。または、重心が 2 つある場合は、ハッシュのペアを検討します。