競技プログラミング - 回文を見つける

こんばんは、りょぶんです。

今日は自分へのメモの内容になります。

競技プログラミングの問題
特定の文字列から回文に該当する文字列のうち、最大長のものを選択する
　＃回分：前から読んでも後ろから読んでも同じになる単語
　＃例：madam, しんぶんし

最適なアルゴリズム
・動的計画法（Dynamic Programming, DP）
・Manacherのアルゴリズム

どちらを選択するか

動的計画法（DP）
理解しやすく、実装も比較的簡単です。O(n^2)の時間複雑度であり、最大文字列長が1000程度であれば実行時間は現実的です

Manacherのアルゴリズム
O(n)の時間複雑度を持ち、より効率的
ただし、前処理とアルゴリズムの理解がやや難しいです。

最大文字列長が1000であれば、より効率的なManacherのアルゴリズムを選択します。理由は、線形時間で動作するため、大きな文字列に対しても高速に回文を見つけることができるため

ただ、残念ながら、私は動的計画法で実装して、問題をクリアしました😓
当然、最適解ではなかったので、順位はあまりよくありませんでした。。
次はManacherで実装してみたいです

アルゴリズムの解説（メモ）

動的計画法（Dynamic Programming, DP）
複雑な問題を解くためのアルゴリズム設計技法であり、以下のようなステップで問題を解決します

1. 部分問題に分割：元の問題を解きやすい部分問題に分解します

2. 部分問題の解を再利用：部分問題の解を記録しておき、再度同じ部分問題を解く必要がないようにします

3. 最適部分構造：部分問題の最適解を利用して、元の問題の最適解を構築します

動的計画法は特に、重複する部分問題が多く存在する場合に有効
計算量を大幅に削減することができ、再帰的なアプローチよりも効率的になります

Manacherのアルゴリズム

文字列内の最長回文部分文字列を線形時間（O(n)）で見つけることができる効率的なアルゴリズムです

1. 前処理：元の文字列に特殊文字（通常は#）を挿入して、すべての部分文字列の長さを奇数にする。これにより偶数長の回文を扱いやすくします

2. 半径配列の計算：各位置を中心とした回文の最大半径を記録します

3. 最長回文の検出：計算された半径配列から、最長の回文部分文字列を抽出します

今日もお読み頂き、ありがとうございました🥰