回文の発掘〜横へな 2013.11.1 参考問題

問題

英数字および下線のみからなる文字列がある。この文字列から何文字か撤去すると回文にすることができる。作ることができる回文のうち、一番長いものの長さを答えよ。

ただし。

回文とは、前から読んでも後ろから読んでもおなじになる文字列である。「a」「aba」「aabbaa」などは回文だが、「ab」「abc」「aabbaaa」などは回文ではない。
英字の大文字小文字は区別する。(つまり、 ABBA は回文だが、 Abba は回文ではない）
入力文字列の長さは高々30文字程度と思って良い。

入力と出力

入力は、回文が埋まっている文字列である。
例えば、「 I_believe_you_can_solve 」のようなものである。

出力は、入力文字列から何文字か撤去して作ることができる回文のうち、最も長いものの文字数である。
「 I_believe_you_can_solve 」から作ることができる最長の回文は、例えば「 evo_n_ove 」なので、この文字列の文字数の10進数表現「 9 」を出力すればよい。

補足

前述のとおり、大文字小文字は区別する。
英数字と下線以外の文字は含まれない。
不正な入力に対処する必要はない。
実装ができた方は Qiitaの記事のコメント欄からリンクを張っていただくと見つけやすくて助かります。
この問題は2013年11月1日に開催される第15回オフラインリアルタイムどう書くの参考問題です。イベントについては ATND の募集ページの方を御覧下さい。

サンプルデータ

#	入力	期待	例
0	`I_believe_you_can_solve`	`9`	`evo_n_ove`
1	`a`	`1`	`a`
2	`aa`	`2`	`aa`
3	`aaa`	`3`	`aaa`
4	`ab`	`1`	`b`
5	`aabb`	`2`	`bb`
6	`ABBA`	`4`	`ABBA`
7	`Abba`	`2`	`bb`
8	`1234567890`	`1`	`0`
9	`1234567890987654321`	`19`	`1234567890987654321`
10	`abcdcba`	`7`	`abcdcba`
11	`0a1b2c3d4c5b6a7`	`7`	`abc4cba`
12	`abcdcba0123210`	`7`	`0123210`
13	`abcdcba_123210`	`7`	`abcdcba`
14	`_bcdcba0123210`	`7`	`0123210`
15	`abcddcba0123210`	`8`	`abcddcba`
16	`abcdcba01233210`	`8`	`01233210`
17	`a0bc1dc2ba3210a`	`9`	`a0123210a`
18	`a0bc1ddc2ba3210`	`8`	`0bcddcb0`
19	`3a0bc1ddc2ba3210`	`10`	`3abcddcba3`
20	`11oooo1111o1oo1o111ooooooooooo`	`20`	`oooo111o1oo1o111oooo`
21	`11o1111o1111oo11ooo11111ooo1oo`	`20`	`o1o1111oo11oo1111o1o`
22	`111111oo11o111ooo1o1ooo11ooo1o`	`21`	`1ooo11ooo1o1ooo11ooo1`
23	`11o1o1o11oo11o11oo111o1o1o11oo`	`27`	`11o1o1o11oo11o11oo11o1o1o11`
24	`oo111o1o11o1oo1ooo11o1o11o1o1o`	`27`	`oo111o1o11ooo1ooo11o1o111oo`
25	`1o1oo11111o1o1oo1o1o1111oo1o1o`	`28`	`1o1oo1111o1o1oo1o1o1111oo1o1`
26	`QQooooQooooQQyQoyQQQyyyyQQoyoy`	`15`	`ooQQyyQQQyyQQoo`
27	`oQoooQooooQyoyQoyoyyyQQyQQQQoQ`	`16`	`QoQQyQyyyyQyQQoQ`
28	`yyyyyooyQyyyoyyQyyooyQoQoQQoQy`	`17`	`yooQyoyyQyyoyQooy`
29	`yyQoyQoyyQyQQoyooooyyQQyQyooQy`	`24`	`yQooyQyQQyooooyQQyQyooQy`
30	`oQQooQoQyQQoyoQQoQyQyQyQoQoooo`	`24`	`oooQoQyQQyoQQoyQQyQoQooo`
31	`oQQyQQyyQyQQoooyQQyyyQQQyyQQoy`	`25`	`oQQyQQyyyQQoooQQyyyQQyQQo`
32	`WAk9iHI4jVDlStyudwTNqE138kwan2`	`3`	`wkw`
33	`c43fIu1Mlz0K9hEVOgGcUdbeB5ksa7`	`3`	`cGc`
34	`CAbYcW5VqHjzFdIkH_61PM0TsyRuie`	`3`	`HkH`
35	`jInQnUvSayrJTsQWujovbbqW0STvoj`	`10`	`jvTWbbWTvj`
36	`iZDrvpUKgtj3FrZsZ4CLjrEgUdZzQG`	`11`	`ZUgrZsZrgUZ`
37	`ROgYUOu6er_DA7nB6UGquO1GUHC62R`	`11`	`RUOu6B6uOUR`
38	`Oh_be_a_fine_girl_kiss_me`	`9`	`e_i_l_i_e`
39	`8086_6502_6809_Z80`	`11`	`8086_2_6808`
40	`xcode_visualstudio_eclipse`	`11`	`ce_iutui_ec`
41	`word_excel_powerpoint_outlook`	`9`	`ol_opo_lo`
42	`abcdefghijklmnopqrstuvwxyz0123`	`1`	`3`

C/C++/Java 用のテストデータ

/*0*/ test( "I_believe_you_can_solve", "9" );    
/*1*/ test( "a", "1" );    
/*2*/ test( "aa", "2" );    
/*3*/ test( "aaa", "3" );    
/*4*/ test( "ab", "1" );    
/*5*/ test( "aabb", "2" );    
/*6*/ test( "ABBA", "4" );    
/*7*/ test( "Abba", "2" );    
/*8*/ test( "1234567890", "1" );    
/*9*/ test( "1234567890987654321", "19" );    
/*10*/ test( "abcdcba", "7" );    
/*11*/ test( "0a1b2c3d4c5b6a7", "7" );    
/*12*/ test( "abcdcba0123210", "7" );    
/*13*/ test( "abcdcba_123210", "7" );    
/*14*/ test( "_bcdcba0123210", "7" );    
/*15*/ test( "abcddcba0123210", "8" );    
/*16*/ test( "abcdcba01233210", "8" );    
/*17*/ test( "a0bc1dc2ba3210a", "9" );    
/*18*/ test( "a0bc1ddc2ba3210", "8" );    
/*19*/ test( "3a0bc1ddc2ba3210", "10" );    
/*20*/ test( "11oooo1111o1oo1o111ooooooooooo", "20" );    
/*21*/ test( "11o1111o1111oo11ooo11111ooo1oo", "20" );    
/*22*/ test( "111111oo11o111ooo1o1ooo11ooo1o", "21" );    
/*23*/ test( "11o1o1o11oo11o11oo111o1o1o11oo", "27" );    
/*24*/ test( "oo111o1o11o1oo1ooo11o1o11o1o1o", "27" );    
/*25*/ test( "1o1oo11111o1o1oo1o1o1111oo1o1o", "28" );    
/*26*/ test( "QQooooQooooQQyQoyQQQyyyyQQoyoy", "15" );    
/*27*/ test( "oQoooQooooQyoyQoyoyyyQQyQQQQoQ", "16" );    
/*28*/ test( "yyyyyooyQyyyoyyQyyooyQoQoQQoQy", "17" );    
/*29*/ test( "yyQoyQoyyQyQQoyooooyyQQyQyooQy", "24" );    
/*30*/ test( "oQQooQoQyQQoyoQQoQyQyQyQoQoooo", "24" );    
/*31*/ test( "oQQyQQyyQyQQoooyQQyyyQQQyyQQoy", "25" );    
/*32*/ test( "WAk9iHI4jVDlStyudwTNqE138kwan2", "3" );    
/*33*/ test( "c43fIu1Mlz0K9hEVOgGcUdbeB5ksa7", "3" );    
/*34*/ test( "CAbYcW5VqHjzFdIkH_61PM0TsyRuie", "3" );    
/*35*/ test( "jInQnUvSayrJTsQWujovbbqW0STvoj", "10" );    
/*36*/ test( "iZDrvpUKgtj3FrZsZ4CLjrEgUdZzQG", "11" );    
/*37*/ test( "ROgYUOu6er_DA7nB6UGquO1GUHC62R", "11" );    
/*38*/ test( "Oh_be_a_fine_girl_kiss_me", "9" );    
/*39*/ test( "8086_6502_6809_Z80", "11" );    
/*40*/ test( "xcode_visualstudio_eclipse", "11" );    
/*41*/ test( "word_excel_powerpoint_outlook", "9" );    
/*42*/ test( "abcdefghijklmnopqrstuvwxyz0123", "1" );

回文の発掘 〜 横へな 2013.11.1 参考問題

問題

入力と出力

補足

サンプルデータ

C/C++/Java 用のテストデータ

回文の発掘〜横へな 2013.11.1 参考問題