第15回オフラインリアルタイムどう書くの参考問題 with ruby

オフラインリアルタイムどう書く
第15回(11月1日) http://atnd.org/events/43825
の、参考問題「回文の発掘」
http://nabetani.sakura.ne.jp/hena/ord15subpalin/
の実装例。

rubyで。

他の言語などの解答例は
http://qiita.com/Nabetani/items/0b56395d4c9e7c64b230
から辿れます。

で。

#!ruby

def solve_impl( s )
  return s.size if s.size<2
  return 2+solve_impl( s[1..-2] ) if s[0]==s[-1]
  last_ix = s.rindex( s[0] )
  [ solve_impl( s.drop(1) ),
    case last_ix
    when 0; 0
    when 1; 2
    else; 2+solve_impl( s[1,last_ix-1] )
    end ].max
end

def solve( s )
  solve_impl( s.chars ).to_s
end

$stdout.sync=true

DATA.each do |line|
  num, src, expected = line.split( /\s+/ )
  actual = solve( src )
  ok = actual==expected;
  puts "%s %s->%s ( %s )" % [ ok ? "ok" : "***NG***", src, actual, expected ]
end

__END__
0 I_believe_you_can_solve 9 evo_n_ove
1 a 1 a
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

いつも通り、テストデータの大半は省略。

概ね順当な実装のつもりの再帰。

ただ、何もしないと遅くなりすぎるので、両端が同じなら迷わず利用するというコード
return 2+solve_impl( s[1..-2] ) if s[0]==s[-1]
を入れて高速化を目論んでみた。
これを入れるとかなり速くなるんだけど、計算量のオーダーはよくわからなくなる。