## C - chokudai Editorial by en_translator

We adopt Dynamic Programming (DP).

Let \(dp[i][j]\) be “the number of combinations of \(j\) characters chosen out of the first \(i\) characters of \(S\) so that the resulting string is equal to the first \(j\) characters of `chokudai`

.

Here, the following recurrence relations are satisfied, where \(N=|S|\) and \(T= \)`chokudai`

:

\(\displaystyle dp[i][j] = \begin{cases} 1 & ( j = 0) \\0 & ( i=0 , 1 \leq j \leq 8) \\dp[i-1][j]& ( 1 \leq i \leq N , 1\leq j \leq 8, S[i] \neq T[j] ) \\dp[i-1][j] + dp[i-1][j-1] & (1 \leq i \leq N , 1\leq j \leq 8, S[i] = T[j])\end{cases}\)

## If you do not understand the reason of the recurrence relations

If \(j=0\)

We have “the first \(0\) characters of`chokudai`

” if and only if no characters is underlined. There are \(1\) such combinations.If \( i=0 \) and \(1 \leq j \leq 8\)

No combinations of characters chosen from the first \(0\) characters of \(S\) is equal to the first \(j (j \geq 1)\) characters of`chokudai`

, so there are \(0\) such combinations.If \(1 \leq i \leq N\) and \(1\leq j \leq 8\)

If \(S[i] \neq T[j]\)

What we want is “the number of combinations of characters chosen out of the first \(i\) characters of \(S\) so that the resulting string is equal to the first \(j\) characters of \(T\).” However, since the \(i\)-th character of \(S\) and the \(j\)-th character of \(T\) are different, we do never underline the \(i\)-th character of \(S\). Therefore, the desired number is equal to “the number of combinations of characters out of the first \((i-1)\) characters of \(S\) so that the resulting string is equal to the first \(j\) characters of \(T\),” that is, \(dp[i-1][j]\).If \(S[i] = T[j]\)

If the \(i\)-th character of \(S\) is not underlined

The number of such combinations is \(dp[i-1][j]\) by the discussion above.If the \(i\)-th character of \(S\) is underlined

The number of such combinations is equal to “the number of combinations of characters chosen from the first \((i-1)\) characters of \(S\) so that the resulting string is equal to the first \((j-1)\) characters of \(T\).”

Overall, the total number is \(dp[i-1][j] + dp[i-1][j-1]\)

One can find every \(dp[i][j]\) in the increasing order of \(i\) and \(j\) with double `for`

statements.

The final result is \(dp[N][8]\).

The computational complexity of this algorithm is \(O(N)\), which is fast enough.

posted:

last update: