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

問題

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

ただし。

入力と出力

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

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

補足

サンプルデータ

# 入力 期待
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 用のテストデータ