回文判定アルゴリズム詳細解析

📊 アルゴリズム概要

この問題はManacher's Algorithmを使用して効率的に解決します。通常の方法では各クエリごとにO(N)時間かかりますが、事前計算によりO(1)時間でのクエリ処理を実現します。

⚡ 計算量分析

時間計算量: O(N + Q) - 前処理O(N) + クエリ処理O(Q)
空間計算量: O(N) - 半径配列のみ
従来手法: O(N × Q) → 最大10^10回の操作
最適化後: O(N + Q) → 最大2×10^5回の操作

🔄 Step 1: 文字列の前処理

偶数長・奇数長の回文を統一的に処理するため、文字間に特殊文字'#'を挿入します。

例: "mississippi"の前処理

元の文字列:

m i s s i s s i p p i

インデックス: 0-10 (長さ11)

前処理後:

# m # i # s # s # i # s # s # i # p # p # i #

インデックス: 0-22 (長さ23)

                        const processed = '#' + s.split('').join('#') + '#'; // "mississippi" →
                        "#m#i#s#s#i#s#s#i#p#p#i#"
                    

🧠 Step 2: Manacher's Algorithm

各位置を中心とした最長回文の半径を効率的に計算します。対称性を利用して無駄な計算を削減します。

アルゴリズムの動作原理

位置	文字	半径	説明
0	#	0	境界
1	m	1	単一文字
7	s	1	"s"単体
9	#	3	"s#s" → 元文字列"ss"
15	#	3	"i#s#s#i" → 元文字列"issi"

🔍 重要な概念

Center: 現在の最長回文の中心位置
Right: 現在の最長回文の右端
対称性の利用: 既に計算した情報を活用して高速化

                        // 対称性を利用した初期化 if (i < right) { radius[i]=Math.min(right - i,
                        radius[2 * center - i]); } // 回文の拡張 while (processed[i + radius[i] +
                        1]===processed[i - radius[i] - 1]) { radius[i]++; }
                    

⚡ Step 3: クエリ処理

事前計算した半径配列を使用して、各クエリをO(1)時間で処理します。

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

1. インデックス変換:

クエリ: L=5, R=8 (1-indexed)
0-indexed: start=4, end=7
部分文字列: "issi"

2. 前処理文字列での位置計算:

center = start + end + 1 = 4 + 7 + 1 = 12
length = end - start + 1 = 7 - 4 + 1 = 4
前処理文字列のインデックス12: "#"

3. 半径チェック:

s # i # s # s # i

radius[12] = 4 ≥ length = 4 → 回文！

                        function isPalindrome(radius: number[], l: number, r: number): boolean {
                        const startIdx = l - 1; // 1-indexed → 0-indexed const endIdx = r - 1; const
                        center = startIdx + endIdx + 1; // 前処理文字列での中心 const len = endIdx -
                        startIdx + 1; // 部分文字列の長さ return radius[center] >= len; // O(1)判定
                        }
                    

📋 全クエリ処理例

入力例の完全解析

クエリ	範囲	部分文字列	中心位置	必要半径	実際半径	結果
1	[5,8]	"issi"	12	4	4	Yes
2	[6,10]	"ssipp"	15	5	3	No
3	[2,8]	"ississi"	9	7	7	Yes

🚀 最適化のポイント

メモリ効率化

配列の再利用: 必要最小限のメモリ使用
型の最適化: TypeScriptの型システム活用
ガベージコレクション考慮: 不要なオブジェクト生成回避

実行時間最適化

事前計算: O(N)時間での前処理
対称性活用: 重複計算の削減
キャッシュ効率: 連続メモリアクセス

🎯 回文判定アルゴリズム詳細解析