最终的网格如下。

我使用下面的公式来计算每个单元格的值。

实现这个公式的伪代码类似于下面这样。

if word_a[i] == word_b[j]:#两个字母相同
    cell[i][j] = cell[i-1][j-1] + 1
else:#两个字母不同
    cell[i][j] = 0

查找单词hish和vista的最长公共子串时，网格如下。

需要注意的一点是，这个问题的最终答案并不在最后一个单元格中！对于前面的背包问题，最终答案总是在最后的单元格中。但对于最长公共子串问题，答案为网格中最大的数字——它可能并不位于最后的单元格中。

我们回到最初的问题：哪个单词与hish更像？ hish和fish的最长公共子串包含三个字母，而hish和vista的最长公共子串包含两个字母。

因此Alex很可能原本要输入的是fish。