こんにちは、Habr。 今日は、さまざまなアルゴリズムの問題を解決する際に多項式ハッシュを使用する方法（以下、単にハッシュ）を書きます。
はじめに
定義から始めましょう。 文字列
s 0..n-1があるとします。 この行の多項式ハッシュは、数
h = hash（s 0..n-1 ）= s 0 + ps 1 + p 2 s 2 + ... + p n-1 s n-1です 。ここで、
pは自然数です（後でどちらかと言われます
。siは文字列
sの i番目の文字のコードです（ほとんどすべての現代言語では
s[i]と書かれてい
s[i] ）。
ハッシュには、同じ文字列のハッシュが必ず等しいという特性があります。 したがって、ハッシュで許可される主な操作は、2つの部分文字列の等価性をすばやく比較することです。
もちろん、2行を比較するために、同様の関数を書くことができます（行
sと
t の長さが一致し、
nに等しいと仮定します）：
boolean equals(char[] s, char[] t) { for (int i = 0; i < n; i++) if (s[i] != t[i]) { return false; } } return true; }
ただし、最悪の場合、この関数はすべての文字をチェックする必要があり、これにより
O（n）の漸近的な動作が得られます。
文字列とハッシュの比較
ハッシュがこれをどのように行うかを見てみましょう。 ハッシュは単なる数字であるため、それらを比較するには
O（1）時間が必要です。 確かに、1つの部分文字列のハッシュを単純な方法で計算するには、
O（n）時間が必要です。 したがって、数式を少しいじり、
O（n） のすべての部分文字列のハッシュ
を一度に見つけることを学ぶ必要があります。 部分文字列
s L..Rと
t X..Y （同じ長さ）を比較してみましょう。 ハッシュ定義を使用して、次のように記述できます。
s L + ps L + 1 + ... + p RL-1 s R-1 + p RL s R = t X + pt X + 1 + ... + p YX-1 t Y-1 + p YX t Y左側で小さな変換を実行します（右側ではすべてが同様に行われます）。 部分文字列
s 0..Rのハッシュを記述します、それが必要です：
ハッシュ（s 0..R ）= s 0 + ps 1 + ... + p L-1 s L-1 + p L s L + p L + 1 s L + 1 + ... + p R-1 s R-1 + p R s Rこの式を2つの部分に分割します...
ハッシュ（s 0..R ）=（s 0 + ps 1 + ... + p L-1 s L-1 ）+（p L s L + p L + 1 s L + 1 + ... + p R-1 s R-1 + p R s R ）... 2番目のブラケットから係数p
Lを抽出します。
ハッシュ（s 0..R ）=（s 0 + ps 1 + ... + p L-1 s L-1 ）+ p L （s L + ps L + 1 + ... + p RL-1 s R-1 + p RL s R ）最初の括弧内の式は、部分文字列
s 0..L-1のハッシュにすぎず、2番目の式には、部分文字列
s L..Rのハッシュが
必要です。 だから、私たちはそれを得ました：
ハッシュ（s 0..R ）=ハッシュ（s 0..L-1 ）+ p Lハッシュ（s L..R ）これは、
ハッシュ（s L..R ）の次の式を意味します。
ハッシュ（s L..R ）=（1 / p L ）（ハッシュ（s 0..R ）-ハッシュ（s 0..L-1 ））同様に、2番目のサブストリングでは、等式
ハッシュ（t X..Y ）=（1 / p X ）（ハッシュ（t 0..Y ）-ハッシュ（t 0..X-1 ））が満たされます。
これらの式を注意深く見ると、部分文字列のハッシュを計算するには、この文字列
のプレフィックスのハッシュ
s 0..0 、
s 0..1 、...、
s 0..n-2 、
s 0のみを知る必要があることがわかります
。 .n-1 また、後続の各プレフィックスのハッシュは前のプレフィックスのハッシュを介して表されるため、それらを線に沿った線形の通過としてカウントするのは簡単です。
O（n）時間で一度にすべて。
pのべき乗も事前に計算し、配列に保存する必要があります。
コード例：
これで完全に武装し、
O（1）の部分文字列2を比較できるようになります。 しかし、すべてがそれほど単純なわけではありません。数式にはいくらかの改良が必要です。 たとえば、同様のコード：
if ((hs[R] - hs[L - 1]) / pow[L] == (ht[Y] - ht[X - 1]) / pow[X]) { ... }
動作しません。
次に、ハッシュを適用できるタスクを詳しく見ていきます。
ハッシュタスク
1.部分文字列の比較
すでに述べたように、最初の、そして最も重要なアプリケーションは、2つのサブストリングの迅速な比較です。ハッシュを使用する他のすべてのアルゴリズムはそれに基づいています。 最後のセクションのコードはやや面倒なので、今後使用するより便利なコードを作成します。
次の関数は、部分文字列
s L..Rに
p Lを掛けたハッシュを計算します。
long getHash(long[] h, int L, int R) { long result = h[R]; if (L > 0) result -= h[L - 1]; return result; }
次に、2つの部分文字列を次の行と比較します。
if (getHash(hs, L, R) * pow[X] == getHash(ht, X, Y) * pow[L]) { ... }
pの累乗による乗算は、「1つの累乗への縮小」と呼ばれます。 最初のハッシュは
p Lで乗算され、2番目のハッシュは
p Xで乗算されます。これは、比較が正しいことを意味します。欠落している係数を乗算する必要があります。
注：部分文字列の長さが一致しているかどうかを最初に確認することは理にかなっています。 そうでない場合、原則として行を等しくすることはできず、上記の条件を確認することはできません。
2. O（n + m）の文字列で部分文字列を検索します
ハッシュを使用すると、文字列内の部分文字列を漸近的に最小限の時間で検索できます。 これは、いわゆるRabin-Karpアルゴリズムによって行われます。
長さ
mの文字列
tのすべての出現を検索する長さ
nの文字列
sがあるとします。 文字列
tのハッシュ（文字列全体）と文字列
sのすべての接頭辞のハッシュを
見つけたら 、部分文字列
s i..i + m-1を比較して、長さ
mのウィンドウで文字列
sに沿って移動
します。
コード：
3. O（n log n）でz関数を見つける
文字列
s のz関数は 、
i番目の要素が文字列
sの位置
iから始まる部分文字列の最長プレフィックスに等しい配列
zであり、これは文字列
s全体のプレフィックスでもあります。 ゼロの位置にあるz関数の値は、文字列
sの長さと等しいと見なされますが、一部のソースではゼロと見なされます（ただし、これは重要ではありません）。
もちろん、
O（n）の z関数
を見つける
アルゴリズムがあり
ます 。 しかし、あなたが知らない、または覚えていない（そしてアルゴリズムがやや面倒な）場合、ハッシュが助けになります。
アイデアは次のとおりです。各
i = 0、1、...、n-1に対して
、バイナリ検索
によって z iを検索します。 各反復で、可能な値の範囲を半分にします。 等式
s 0..k-1 = s i..i + k-1は、
z i未満のすべての
kに対して必然的に成り立ち、大きな
kに対しては成り立ちません。
コード：
int[] z = new int[n]; for (int i = 0; i < n; i++) { int left = 1, right = n - i;
4. O（n log n）で辞書編集的に最小の循環改行を検索します 。
O（n）でこの問題を解決できる
Duvalアルゴリズムがありますが、それを理解していないかなり強力なOlympiadプログラマを知っています。 彼らがそれを理解している限り、再びハッシュを使用します。
アルゴリズムは次のとおりです。 まず、最良の（辞書編集的に最小限の）答えを得るためにstringを使用します。 次に、各巡回シフトについて、バイナリ検索を使用して、このシフトの最大共通プレフィックスの長さと現在のベストアンサーを見つけます。 その後、このプレフィックスに続く文字を比較し、必要に応じて回答を更新するだけで十分です。
また、便宜上、文字列
sをそれ自体に帰属させることをお勧めします。文字列
sの文字にアクセスするときにモジュロ演算を行う必要はありません。 これはすでに行われていると想定しています。
コード：
int bestPos = 0; for (int i = 1; i < n; i++) { int left = 1, right = n, length = 0;
注：実際、コンパレータは辞書式に2つの循環シフトを比較する
forループ内に記述されて
forます。 これを使用すると、
O（n log 2 n）のすべての巡回シフトをソートでき
ます 。
5. O（n log n）の行ですべての回文を検索します 。
繰り返しますが、この問題の
解決策は
O（n）にあります。 そして再び、ハッシュでそれを解決します。
部分文字列
s L..Rは、
s L = s R 、
s L + 1 = s R-1などの場合、回文と呼ばれます。 ロシア語で言えば、左から右へ、右から左へ同じように読まれることを意味します。
おそらく、ハッシュがそれと何の関係があるのかをすでに知っているか、推測しているでしょう。 部分文字列
s 0..0 、
s 0..1 、...、
s 0..n-2 、
s 0..n-1のハッシュを含む配列
h[]加えて、2番目の配列
rh[] （ 「反転」線）、これを右から左に移動します。 それに応じて、ハッシュ
s 0..n-1 、
s 1..n-1 、...、
s n-2..n-1 、
s n-1..n-1が含まれます。
rh[n - 1] = s[n - 1]; for (int i = n - 2, j = 1; i >= 0; i--, j++) { rh[i] = rh[i + 1] + pow[j] * s[i]; }
O（1）の後の文字列が回文であるかどうかを判断する方法はすでに明確になっているはずです。 getHash（）と同様のgetRevHash（）関数を作成し、必要な比較条件を指定します。 この式の正確性は、記事の冒頭で示したものと同様の数学的計算を行うことで独立して検証できます。
long getRevHash(long[] rh, int L, int R) { long result = rh[L]; if (R < n - 1) result -= rh[R + 1]; return result; } boolean isPalindrome(long[] h, long[] rh, long[] pow, int L, int R) { return getHash(h, L, R) * pow[n - R - 1] == getRevHash(rh, L, R) * pow[L]; }
次に、行の
iの位置を検討します。 位置
iを中心とする奇数の長さ
dのパリンドロームがあるとします（偶数の場合、位置
i-1と
iの間を中心とします）。 1つのキャラクターを端から切り取ると、パリンドロームのままになります。 そして、その長さがゼロになるまで継続できます。
したがって、各位置に2つの値を格納するだけで十分です。位置
iに中心を持つ奇数長のパリンドロームがいくつ存在するか、位置
i-1と
iの間に中心がある偶数長のパリンドロームがいくつあります。 これら2つの値は互いに完全に独立しているため、別々に処理する必要があることに注意してください。
前と同様に、バイナリ検索を適用します。
int[] oddCount = new int[n]; for (int i = 0; i < n; i++) { int left = 1, right = min(i + 1, n - i); while (left <= right) { int middle = (left + right) / 2; if (isPalindrome(h, rh, pow, i - middle + 1, i + middle - 1)) { oddCount[i] = middle; left = middle + 1; } else { right = middle - 1; } } } int[] evenCount = new int[n]; for (int i = 0; i < n; i++) { int left = 1, right = min(i, n - i); while (left <= right) { int middle = (left + right) / 2; if (isPalindrome(h, rh, pow, i - middle, i + middle - 1)) { evenCount[i] = middle; left = middle + 1; } else { right = middle - 1; } } }
これで、たとえば、行内のすべての回文の総数、または最大回文の長さを見つけることができます。 位置
iを中心とする最大奇数パリンドロームの長さは
2 * oddCount[i] - 1 、最大偶数パリンドロームは
2 * evenCount[i]です。
偶数および奇数の長さの回文にはさらに注意する必要があることをもう一度思い出させてください。原則として、それらは互いに独立して処理されなければなりません。
マトリックスハッシュ
最後に、ハッシュのより洗練された使用を検討してください。 これで、空間が2次元になり、部分行列を比較します。 幸いなことに、ハッシュは2次元の場合に非常によく一般化されています（3次元以上を見たことはありません）。
数字
pと
pow配列の代わりに、2つの異なる数字
p 、
qと2つの
pow1 、
pow2 。それぞれの方向に1つの数字と1つの配列があります。
ハッシュ行列
a 0..n-1、0..m-1は
、量
p i q j aのすべての
i = 0、...、n-1 、
j = 0、...、m-1の合計と呼ばれ
ます。 ij 。
ここで、左上の要素
a 00を含む部分行列のハッシュをカウントする方法を学びます。 明らかに、
ハッシュ（a 0..0、0..0 ）= a 00 。 ほとんどすべての
j = 1、...、m-1 hash（a 0..0、0..j ）= hash（a 0..0、0..j-1 ）+ q j a 0j 、すべての
i = 1、...、n-1 hash（a 0..i、0..0 ）= hash（a 0..i-1、0..0 ）+ p i a i0 。 これは、1次元の場合から直接続きます。
サブマトリックス a 0..i、0..jのハッシュを計算する方法は？
ハッシュ（ 0..i、0..j ）=ハッシュ（a 0..i-1、0..j ）+ハッシュ（a 0..i、0..j-1 ）-ハッシュ（a 0..i-1、0..j-1 ）+ p i q j a ij 。 この式は、次の考慮事項から取得できます。
サブマトリックス a 0..i-1、0..jおよび
0..i、0..j-1のハッシュを構成するすべての用語を加算します（ハッシュ、これはいくつかの用語の合計です）。 。 同時に、部分行列
a 0..i-1、0..j-1を構成する項を2回考慮したので、それらを1回考慮するように減算します。 ここで、要素
a ijに対応する
pと
qのべき乗を掛けたもののみが欠落しています。
記事の最初の部分とほぼ同じ理由で（包含/除外式の関与にすでに気付いていますか？）、任意の部分行列
a x1..x2、y1..y2のハッシュを計算する関数が構築されます。
long getMatrixHash(long[][] h, int x1, int x2, int y1, int y2) { long result = h[x2][y2]; if (x1 > 0) result -= h[x1 - 1][y2]; if (y1 > 0) result -= h[x2][y1 - 1]; if (x1 > 0 && y1 > 0) result += h[x1 - 1][y1 - 1]; return result; }
この関数は、部分行列
a x1..x2、y1..y2 × p x1 q y1のハッシュを返します。
2つの部分行列
ax1..ax2、ay1..ay2と
bx1..bx2、by1..by2の比較は、次の式を使用して実行されます。
if (getMatrixHash(h, ax1, ax2, ay1, ay2) * pow1[bx1] * pow2[by1] == getMatrixHash(h, bx1, bx2, by1, by2) * pow1[ax1] * pow2[ay1]) { ... }
ハッシュはまた、最大の対称部分行列を見つけることに関連する問題を解決できます。 また、この作業を実行するアルゴリズムが、スピードと単純さの点でハッシュに匹敵するものかどうかもわかりません。 ここでは、1次元の場合のパリンドロームの検索と同じ原理が使用されます（つまり、右から左、下から上へ「逆」ハッシュをカウントし、偶数と奇数の長さの部分行列に対して別々にビン検索を実行します）。 この問題を自分で解決することをお勧めします-この記事は役に立ちます！
おわりに
したがって、自由に使用できる非常に優れた装置があり、可能な限り最高の漸近法を使用するか、専用アルゴリズムよりもわずかに（対数倍）遅いだけで多くのことを実行できます。 悪くないですか？