\(S = a + b\) と分ける方法を全探索し、\(a\) が \(A\) の部分列となるか、\(b\) が \(B\) の部分列となるかを調べることを考えます。

ここで、\(S\) の前 \(x\) 文字が \(A\) の部分列であるとき、\(S\) の前 \(y\) 文字 (\(y \le x\)) もまた \(A\) の部分列となります。

したがって、\(S\) の前何文字までが \(A\) の部分列となるかという境界が存在します。 また同様に、\(S\) の後ろ何文字までが \(B\) の部分列となるかという境界も求めると、簡単に答えを計算することができます。

\(S\) の前何文字までが \(A\) の部分列となるかという境界を、前の文字から順番に比較して \(O(|S| + |A|)\) 時間で求めると部分点を得られます。
これを満点にするには、\(O(|S|)\) 時間で求める必要があります。そこで、\(A\) の各位置において「次にいつ文字 \(c\) が出現するか」のテーブルを求めておくと、\(O(|S|)\) 時間で求めることができます。

実装例 (C++)