http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2261
15文字以下の制限があるのでO(2^n)で全探索できるがDPも可能
ただし全探索の場合、iwiを軸として対称であることに注意する
iwiの左右の文字列をs, tとして、以下に2つの解法を述べる
2つ目の解法の説明はする内容がない上、UVa11151 Longest Palindromeとほぼ同じであるので省略
ここでは1つ目の解法のみについて考える
s, tのそれぞれの文字列に対し、1文字ずつ「削る」「削らない」の2択でビットを使いfor文を回し文字列の集合をつくる
for( int S=0; S < (1<<s.size()); S++ ) { for( int T=0; T< (1<<t.size()); T++ ) { ss = sからビットの集合Sを用いて文字列を作成 tt = tからビットの集合Tを用いて文字列を作成 } }
上のコードは例えば文字列ABCDに対し、
A B C D ( _ を空文字列として表記) ------------------------ _ _ _ _ 0000 (全て削る) _ _ _ D 0001 _ _ C _ 0010 _ _ C D 0011 _ B _ _ 0100 _ B _ D 0101 _ B C D 0111 A _ _ _ 1000 A _ _ D 1001 A _ C _ 1010 A _ C D 1011 A B _ _ 1100 A B _ D 1101 A B C _ 1110 A B C D 1111 (1つも削らない)
となるような文字列を作るものである。上の ビット集合S から各の文字 A, B, C, D の存在を確認するにはどうすればよいだろうか
これは例えば以下のように、存在の有無を調べたい文字に当たるビットを最下位に落として1との論理積を見れば良い。s = "ABCD"として、
for( int i=0; i< s.size(); i++) { if( S >> i & 1 ) { // 存在 ss = s[str.size()-1-i] + ss; } }
と書ける。またここで、上のビット集合と文字の存在の関係表において
_ _ _ _ 0000 A _ _ _ 0001 _ B _ _ 0010 A B _ _ 0011 _ _ C _ 0100 ・・・
と充てるように考えれば、ssを作る部分は
ss += s[i];
と簡単に書ける