UVa11151 Longest Palindrome


※上記の広告は60日以上更新のないWIKIに表示されています。更新することで広告が下部へ移動します。

UVa11151 Longest Palindrome

サイト

http://uva.onlinejudge.org/index.php?option=onlinejudge&page=show_problem&problem=2092

解説

以下の2つ解法がある

  1. DFS
  2. DP 最長共通部分列問題
解法1
AABCEAG

という文字列でDFSを考えてみる。まず、

A  ABCEA  G

と分ける。AとGは異なるので、右端のGを取り除いた文字列と左端のAを取り除いた文字列でdfsをすることになる。よって返す値は

return max( dfs( AABCEA ), dfs( ABCEAG ) )

となり解は2つのdfsの最大値に限定出来る。ここで左のdfs

AABCEA

について考える。以下のように

A  ABCE  A

と分けると、左右のAは一致しているので返す値は

return dfs( ABCE ) + 2

である。また、右のdfsにおいては左端と右端が異なるのではじめと同様に2つの文字列に分割してdfsする。

後は再帰の終了条件を指定してやれば終わり

解法2

入力の文字列sに対し、t = rev(s) を考える。sとtで最長共通部分列問題として解くと解が求まる。蟻本の内容をそのまま使うと、解はdp[n][n]となる。