\(S\) を反転させた文字列を \(rev(S)\) と表記します。

\(S\) に対して「同じ文字が隣り合う箇所を削除すること」を削除できなくなるまで繰り返してできる文字列を \(T\) とすると、\(S + rev(T)\) はバーガーとなります。

ここで、全バーガーである文字列 \(\Leftrightarrow\) バーガーのうち先頭と末尾が同じである文字列、が成り立ちます。

そのため \(S + rev(T)\) の先頭と末尾が同じ文字なら \(rev(T)\) がそのまま答えとなり、そうでないなら \(rev(T)+ S_1 + S_1\) が答えとなります。

最初の \(T\) の求め方ですが、以下の手順により求めることができます。

• 空文字列 \(T\) に対しで、\(c = S_1,S_2, \dots, S_{|S|}\) の順に以下を行う。
  • \(T\) の末尾が \(c\) であるなら \(T\) の末尾の文字を削除する。
  • そうでないなら \(T\) の末尾に \(c\) を追加する。