最長の一致部分列求めたって駄目だろ

a*b*c*d*e***e*d*c*b*a

として、*には反転したものが一致する部分列を持たないように入れる。
しかし、*を取り除くことで最低でも、abcdeを含む回文が作れる