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}$ ...