Detour: Finding a Longest Common Subsequence

The other way of finding LCS

Define the i-prefix of a string as the substring formed by its first i letters and the j-suffix of a string as the substring formed by its final j letters. Also, given strings ${v}$ and ${w}$, let LCS$_{i, j}$ denote an LCS between the i-prefix of ${v}$ and the j-prefix of ${w}$, and let ${s}_{i, j}$ be the length of LCS$_{i, j}$.

By definition, ${s}_{i, 0}$ = ${s}_{0, j}$ = 0 for all values of i and j. Next, LCS ...