「UVa11151 Longest Palindrome」の編集履歴（バックアップ）一覧はこちら
追加された行は緑色になります。
削除された行は赤色になります。
*UVa11151 Longest Palindrome
**サイト
http://uva.onlinejudge.org/index.php?option=onlinejudge&page=show_problem&problem=2092
**解説
以下の2つ解法がある
+DFS
+DP 最長共通部分列問題
***解法1
>||
AABCEAG
||<
という文字列でDFSを考えてみる。まず、
>||
A ABCEA G
||<
と分ける。AとGは異なるので、右端のGを取り除いた文字列と左端のAを取り除いた文字列でdfsをすることになる。よって返す値は
>||
return max( dfs( AABCEA ), dfs( ABCEAG ) )
||<
となり解は２つのdfsの最大値に限定出来る。ここで左のdfs
>||
AABCEA
||<
について考える。以下のように
>||
A ABCE A
||<
と分けると、左右のAは一致しているので返す値は
>||
return dfs( ABCE ) + 2
||<
である。また、右のdfsにおいては左端と右端が異なるのではじめと同様に2つの文字列に分割してdfsする。
後は再帰の終了条件を指定してやれば終わり
***解法2
入力の文字列sに対し、t = rev(s) を考える。sとtで最長共通部分列問題として解くと解が求まる。蟻本の内容をそのまま使うと、解はdp[n][n]となる。
