Manacherアルゴリズムによる回文解析の効率的処理
問題の背景
文字列 s が与えられ、その中にある最長の連続する回文部分文字列の長さを求めたいとします。単純なアプローチとしては、すべての部分文字列を列挙し、それぞれが回文かどうかを判定する方法がありますが、これは O(n^3) の計算量となり非効率です。
より良い方法として、各位置を中心として左右に拡張していく O(n^2) アルゴリズムが考えられます。この方法で ...
6月8日 23:54 投稿
Pythonの実験と課題 - 04 データ型、数学関数、文字列
提出期限
実験目標
以下の内容を習熟します：
forループとturtleの活用
数値演算子
mathライブラリの基本関数
文字列から数値型への変換(int, float, complex)
文字列操作の基本関数
実験内容
課題1. whileループをforループに置き換える円生成プログラム
参考コード：
def calculate_area(radius):
return 3.14 * radius * radius
n = i ...
6月3日 16:37 投稿
回文部分文字列と回文部分列の動的計画法による解法
回文部分文字列のカウント
この問題の難しさは、DP配列の定義と漸化式の構築にあります。直接dp[i]を[0,i]の部分文字列に含まれる回文の数と定義すると、漸化式を見つけることができません。回文の性質を利用して、次のような漸化式を構築できます：[i,j]が回文かどうかを判断するために、s[i] == s[j]の場合は[i+1,j-1]が回文かどうかを確認するだけで済みます。s[i] != s ...
6月1日 11:09 投稿