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: