SRM663 div.1 300 ABBADiv1

問題

ABBADiv1
A, Bのみからなる文字列initialとtargetが与えられる。このとき、initialに以下の2種類の操作を繰り返し行って、targetに変換できるか?

• 文字列にAを付け加える
• 文字列にBを付け加えて、文字列をひっくり返す

制約

解法

initialから変換していく途中の文字列は、targetもしくはreverse(target)に部分文字列として含まれていないといけない。
target、reverse(target)の部分文字列は合計O(|target|^2)個しか存在しないので、深さ優先探索で調べていけばよい。

コード

最大で49msだった。