以下 0-indexed とする。

条件を満たす \(A\) の構造を考える。

\(A\) を先頭から見て初めて \(X_0\) が現れるインデックスが \(t\) であったとする。

条件から \(A[t + 1: N]\) において、\(X[1 : M]\) は現れない。

\(p \neq X_0\) については \((p, X_1, \ldots, X_{M-1})\) が部分列として現れる必要があることから、\(A[0 : t + 1]\) において、\((p, X_1)\) が部分列として現れる必要がある。 つまり、\(A\) の prefix について、

\(p \neq X_0\) がすべて現れた後に \(X_1\) が現れ、その後 \(X_0\) が 初めて 現れる。(ただし、\(X_0 = X_1\) の場合は \(X_1\) に関する条件が自然に満たされる。)

という条件が満たされている必要がある。

この条件が満たされたとき、考える必要がある部分列は \(X_0\) から始まるもののみなので、\((A, X) = (A[t + 1 : N], X[1 : M])\) と取り替えたものについて、同様の条件を満たせばよいことがわかる。

このことから、以下のように \(dp\)[\(i\)][\(j\)][\(k\)][\(c\)] を定義することで動的計画法が設計できる。

\(i\) : \(A\) の先頭何項を決めたか

\(j :\) 考えている \(X\) が \(X[j : M]\)

\(k: \) \(X_j \neq p\) のうち、\(K\) 種類が現れた

\(c: \) \(K - 1\) 種類すべてが現れたあとに、\(X_{j + 1}\) が登場したかどうか

答えは \(dp[N][M - 1][K - 1][0]\) である。 また、dp の遷移は定数個なので、この問題を \(O(NMK)\) で解くことができた。

ところで、dp の遷移を考えると \(j\) が 1 増えるのに、\(i\) は少なくとも \(K\) 回増加する必要がある。 このことから、\(N < MK - 1\) ならば答えは \(0\) である。

よって、\(O(MK) = O(N)\) とみなすことができ、全体で \(O(N^2)\) でこの問題を解くことができた。