私自身が表題の問題を解いた時のプログラムについて解説します。
問題の詳細は「回文に分ける」（CodeIQ）を参照してください。
【概要】
文字列を、二文字以上の回文の集まりに分ける方法が、何通りあるのかを数えてください。
【入出力】
入力は
aaabcbaaaa
のようになっています。
アルファベットの小文字だけの文字列です。
出力するのは、分ける方法が何通りあるかです。
先ほどの入力の場合は
aa/abcba/aaa
aaa/bcb/aaaa
aaa/bcb/aa/aa
のように、3 通りあるので、
aaabcbaaaa
に対応する出力は
3
になります。
【例】
入力 出力 分け方 aaabcbaaaa 3 aaa/bcb/aa/aa
aaa/bcb/aaaa
aa/abcba/aaa
ababcdcbaazzaa 2 aba/bcdcb/aa/zz/aa
aba/bcdcb/aazzaa
abcdedcba 1 abcdedcba
【補足】
不正な入力に対処する必要はありません。
文字列の長さは 1 文字以上で、 50 文字を超えることはありません。
全体をそのまま使うという分け方もひとつに数えます。
Rubyで解答しています。
#!/usr/bin/ruby
$Memo = {}
def isKaibun(line)
for i in 0...line.size
j = line.size - i - 1
break if i > j
return false if line[i] != line[j]
end
return true
end
def solve(line)
return $Memo[line] if $Memo[line] != nil
return 0 if line.size < 2
ret = isKaibun(line) ? 1 : 0
for i in 1...line.size
l = line[0..i]
r = line[i+1..-1]
# printf("%s, %s, %s, %s\n", l, r, isKaibun(l).to_s, isKaibun(r).to_s)
next if !isKaibun(l)
ret += solve(r)
end
$Memo[line] = ret
return ret
end
# main
while line = gets
line.strip!
next if line.empty?
p solve(line)
end
わかりやすい問題と思います。
この出題者の問題としては珍しいタイプかもしれません。
入力値をsolve()に渡し、結果を印字します。
$Memoはある文字列の分解を行った結果を記録しておく領域です。
考え方に書いた処理を行います。
$Memoに引数の文字列の結果があれば操作ずみなので$Memoの結果を返します。
引数lineの長さが2未満なら回文ではなくなるので0を返します。
line自体が回文かをチェックし、回文なら返却値retを1、そうでなければ0にします。
lineから2,3,4,…,文字列の長さだけ先頭から文字列を切り出します。
lは切り出した文字列、rはその残りです。
lが回文で無いならうまく分けられていないので無視します。
solve()の引数にrを渡して再帰的に処理し、返却値を加算します。
$Memoにその時の引数lineをキー、retを値として記録します。
retを返却します。
lineが回文かどうかをチェックします。
文字列の両端から中央に向かって文字が同じかをチェックします。
どこかで違っていたら回文では無いのでfalseを返却します。
iは先頭からの位置（インデックス番号）、jは末尾からの位置（インデックス番号）なのでi>jになったら真ん中を超えたので処理をやめます。
最後まで違いがなければ回文なのでtrueを返します。
問題を読んだ瞬間に、メモ化再帰で普通にできるなぁ、と思いました。
少し考えたのがコードの18行目の所で、回文を見つけたら1をreturnだとその文字列をさらに複数の回文にできる場合にうまく行かないのでreturnせずに処理する所くらいでしょうか。と言っても大した問題では無く、シンプルな問題だと思いました。