Pair Deletion

初期状態を $i = 1, j = 1$ として空のスタックを $1$ つ用意し、$i \leq |S|$ を満たす間、以下の遷移を考えます。

• $S_i$ = $T_j \ (i \leq |S|, j \leq |T|)$ でスタックが空である時、$i, j$ 両方に $1$ を加える。
• そうでないとき、スタックに $S_i$ を追加し、$i$ に $1$ を加える。 スタックの後ろ $2$ つの要素が同じとき、これら $2$ 文字をスタックから削除する。

この操作を行った後、$j = |T|$ かつスタックが空の時、$S = T$ を達成することができます。