BigInt + 二重ハッシュアルゴリズム詳細解析

🧠 アルゴリズム概要

二重ローリングハッシュを使用して回文判定を行います。文字列を数値化し、前方向と後方向のハッシュ値を比較することで、O(1)時間での高速判定を実現します。

⚡ パフォーマンス比較

手法	前処理	クエリ処理	総時間	精度	実装難易度
単純判定	O(1)	O(N)	O(Q×N)	100%	★☆☆
Manacher	O(N)	O(1)	O(N+Q)	100%	★★★
二重ハッシュ	O(N)	O(1)	O(N+Q)	99.999%	★★☆

🔢 Step 1: ローリングハッシュの基本原理

文字列を多項式として数値化し、効率的に部分文字列のハッシュ値を計算します。

ハッシュ関数の定義

hash(s) = (s[0]×base^(n-1) + s[1]×base^(n-2) + ... + s[n-1]×base^0) mod p

例: "abba"のハッシュ計算

a b b a

hash₁ = (97×257³ + 98×257² + 98×257¹ + 97×257⁰) mod 10⁹+7
hash₂ = (97×263³ + 98×263² + 98×263¹ + 97×263⁰) mod 10⁹+9

🎯 BigIntの利点

精度保証: JavaScript標準のNumber(53bit)制限を回避
オーバーフロー防止: 任意精度演算
大きな法の使用: 10⁹+7, 10⁹+9レベルの素数を安全に使用

🔄 Step 2: 前方向・後方向ハッシュの事前計算

文字列を両方向からハッシュ化し、回文判定の準備を行います。

例: "mississippi"の両方向ハッシュ

前方向ハッシュ（左→右）:

m i s s i s s i p p i

Forward Hash₁: h[0], h[1], h[2], ..., h[11]

後方向ハッシュ（右→左）:

i p p i s s i s s i m

Backward Hash₁: b[11], b[10], b[9], ..., b[0]

                        // 前方向ハッシュ計算
                        for (let
                        i =
                        0; i
                        < n;
                        i++) {
                        const charCode
                        = BigInt(s.charCodeAt(i)); forwardHash1[i
                        + 1]
                        = (forwardHash1[i] *
                        BASE1 +
                        charCode) %
                        MOD1;
                        forwardHash2[i
                        + 1]
                        = (forwardHash2[i] *
                        BASE2 +
                        charCode) %
                        MOD2; }

                        // 後方向ハッシュ計算
                        for (let
                        i =
                        n -
                        1; i
                        >= 0;
                        i--) {
                        const charCode
                        = BigInt(s.charCodeAt(i)); backwardHash1[i] = (backwardHash1[i +
                        1] *
                        BASE1 +
                        charCode) %
                        MOD1;
                        backwardHash2[i]
                        = (backwardHash2[i +
                        1] *
                        BASE2 +
                        charCode) %
                        MOD2; }
                    

🎯 Step 3: 二重ハッシュによる回文判定

前方向と後方向のハッシュ値を比較して回文を判定します。2つの異なるハッシュ関数を使用することで、衝突確率を劇的に減少させます。

具体例: クエリ[5,8] → "issi"の判定

1. 部分文字列の特定:

m i s s i s s i p p i

対象: "issi" (インデックス 4-7)

2. ハッシュ値計算:

前方向ハッシュ

Hash₁: getForwardHash(4, 7)

Hash₂: getForwardHash(4, 7)

後方向ハッシュ

Hash₁: getBackwardHash(4, 7)

Hash₂: getBackwardHash(4, 7)

3. 比較結果:

ハッシュ種類	前方向値	後方向値	一致
Hash₁ (base=257)	計算中...	計算中...	-
Hash₂ (base=263)	計算中...	計算中...	-
最終判定	両方のハッシュが一致		Yes

                        function
                        isPalindrome(data: PrecomputedData,
                        l: number,
                        r: number):
                        boolean {
                        // 前方向と後方向のハッシュ値を計算
                        const
                        forwardHash =
                        getForwardHash(data, l-1, r-1);
                        const
                        backwardHash =
                        getBackwardHash(data, l-1, r-1);

                        // 二重ハッシュで判定
                        return
                        forwardHash.hash1
                        ===
                        backwardHash.hash1
                        &&
                        forwardHash.hash2
                        ===
                        backwardHash.hash2; }
                    

🔐 Step 4: 衝突確率の分析

ハッシュ衝突確率の理論分析

📊 単一ハッシュの場合

衝突確率: 約 1/10⁹
信頼性: 99.9999999%
リスク: 大量データで稀に誤判定

🎯 二重ハッシュの場合

衝突確率: 約 1/10¹⁸
信頼性: 99.999999999999999%
リスク: 実質的にゼロ

P(両方衝突) = P(Hash₁衝突) × P(Hash₂衝突)
≈ (1/10⁹) × (1/10⁹) = 1/10¹⁸

📊 Step 5: メモリ使用量分析

メモリ効率の詳細

データ構造	サイズ	目的	最大メモリ (N=10⁵)
forwardHash1[]	(N+1) × 8 bytes	前方向第1ハッシュ	808 KB
forwardHash2[]	(N+1) × 8 bytes	前方向第2ハッシュ	808 KB
backwardHash1[]	(N+1) × 8 bytes	後方向第1ハッシュ	808 KB
backwardHash2[]	(N+1) × 8 bytes	後方向第2ハッシュ	808 KB
power1[], power2[]	2 × (N+1) × 8 bytes	累乗値キャッシュ	1616 KB
合計	6 × (N+1) × 8 bytes	-	約 4.8 MB

💡 メモリ最適化のポイント

配列の事前確保: ガベージコレクション負荷軽減
BigInt効率化: 不要な中間値の生成回避
累乗キャッシュ: 重複計算の排除

⚖️ Step 6: アルゴリズム比較分析

🎯 実装複雑性 vs パフォーマンス

観点	Manacher's Algorithm	BigInt + 二重ハッシュ
実装難易度	高（複雑な境界処理）	中（直感的なハッシュ計算）
デバッグ容易性	困難（インデックス計算複雑）	容易（ハッシュ値で確認可能）
メモリ使用量	O(N) - 1配列	O(N) - 6配列
精度	100%（確定的）	99.999%（確率的）
拡張性	回文専用	文字列照合汎用

🔧 実装の安定性比較

❌ Manacher's Algorithmの課題

境界エラー: 複雑なインデックス計算
奇偶処理: 統一的でない処理
デバッグ困難: エラー原因の特定が難しい
実装ミス: 微細なバグが発生しやすい

✅ 二重ハッシュの利点

実装安全性: 単純で理解しやすい
統一処理: 奇数長・偶数長を同様に処理
デバッグ容易: ハッシュ値で動作確認
拡張性: 他の文字列問題にも応用可能

🚀 Step 7: 実装の詳細とコツ

💎 BigInt使用時の注意点

                        // ❌ 間違った使用法
                        const result
                        = hash
                        + charCode;
                        // Number + BigInt エラー

                        // ✅ 正しい使用法
                        const result
                        = hash
                        + BigInt(charCode); // BigInt + BigInt

                        // ❌ 効率の悪い書き方
                        const mod
                        = (((a
                        % MOD)
                        + MOD)
                        % MOD);
                        // 冗長

                        // ✅ 効率的な書き方
                        const mod
                        = (a
                        % MOD
                        + MOD)
                        % MOD;
                        // 最適化済み
                    

🎯 パフォーマンス最適化テクニック

累乗の事前計算: power[i] = base^i をO(N)で計算
モジュラ演算の最適化: 負数処理を効率化
BigInt変換の最小化: 必要な箇所のみでBigInt使用
配列アクセスパターン: キャッシュ効率を考慮

📈 Step 8: 全体クエリ処理の流れ

入力例の完全解析

クエリ	範囲	部分文字列	前方向Hash₁	後方向Hash₁	Hash₁一致	Hash₂一致	最終結果
1	[5,8]	"issi"	xxxxx1	xxxxx1	✓	✓	Yes
2	[6,10]	"ssipp"	xxxxx2	yyyyy2	✗	✗	No
3	[2,8]	"ississi"	xxxxx3	xxxxx3	✓	✓	Yes

🎖️ アルゴリズムの総合評価

🏆 BigInt + 二重ハッシュの優位性

✨ 主要なメリット

実装の安全性: 境界エラーが発生しにくい
デバッグの容易さ: ハッシュ値で動作確認可能
高い信頼性: 99.999%の精度保証
実行速度: O(N+Q)の効率的な処理
スケーラビリティ: 大規模データにも対応

総合評価: 実用性 ★★★★★ | 実装難易度 ★★☆☆☆ | パフォーマンス ★★★★★

🎯 BigInt + 二重ハッシュアルゴリズム詳細解析