1/26
Loading...
🔍パターン検索問題
📝 今日の問題 テキスト: "HELLO WORLD HELLO" 探すパターン: "HELLO" 🎯 目標: テキストでパターンがどこにあるか探す! ❌ 単純な方法: 全位置で5文字ずつ比較 → 最悪O(n×m) = 多くの比較が必要 ✅ もっと速い方法があります!
Loading...
📝 今日の問題 テキスト: "HELLO WORLD HELLO" 探すパターン: "HELLO" 🎯 目標: テキストでパターンがどこにあるか探す! ❌ 単純な方法: 全位置で5文字ずつ比較 → 最悪O(n×m) = 多くの比較が必要 ✅ もっと速い方法があります!
文字列ハッシングは文字列を固有の数値（ハッシュ値）に変換する技法です。 多項式ハッシュ公式: hash = (c[0]×p^(n-1) + c[1]×p^(n-2) + ... + c[n-1]) mod m c[i]はASCIIコード、pは基数（通常31）、mは大きい素数です。 ローリングハッシュでウィンドウ移動時にO(1)で新ハッシュ計算、パターンマッチングでO(n+m)を達成!