以下のような区間 DP (動的計画法) を考えます。

\(\mathrm{dp}[l][r]\) : \(S\) の \(l\) 文字目から \(r\) 文字目までを取り出した文字列から \(T\) が何回取り除けるか。

\(\mathrm{dp}[1][N]\) が最終的な答えです。
ここで \(\mathrm{dp}[l][r]\) は以下のいずれかの一番大きいものです。

• \(\mathrm{dp}[l + 1][r]\) (\(l\) 文字目は消さないということにする場合)
• \(\mathrm{dp}[l][r - 1]\) (\(r\) 文字目は消さないということにする場合)
• (ある \(m\) が存在して \(l \lt m \lt r, \mathrm{dp}[l][m - 1] = m - l, \mathrm{dp}[m + 1][r] = r - m, (S_l, S_m, S_r) = (T_1, T_2, T_3)\) な場合のみ) : \(r - l + 1\) (\(S_l\) と \(S_m\) の間、\(S_m\) と \(S_r\) の間は全部消し、その後 \(S_l, S_m, S_r\) を消す場合 )
• \(l \le m \lt r\) を満たす \(m\) について、\(\mathrm{dp}[l][m] + \mathrm{dp}[m + 1][r]\) (区間を分けて考える場合 (例えば \(S_l\) または \(S_r\) を取り除くが、一つ上の項のような取り除き方ではない場合))

よって \(m\) を \(O(N)\) 通り試しても全体で \(O(N^3)\) で答えが求まります。