如果A=a[1]a[2]…a[m]是一个长度为m的字符串, 把其中的若干(可能是0个, 也可能是n)个符号去掉, 而得到一个新字符串, 这个新字符串就称为A的子序列(Subsequence). 例如, 若A=abc0123, 那么b02, abcl23, b3, c, ab0123, ab12等都是A的部分序列.

假设给出两个字符串A与B, 长度分别是m与n, 那么A与B就含有若干共同的子序列, 至少虚字符串(或说是空字符串)就是一个共同部分序列; 所谓C是A与B的公共子序列, 指的是C是A的子序列, C也是B的子序列。编写一个程序,把A与B的公共子序列中最长的那一个找出来。

这个同题一般都称为最长公共子序列(Longest Common Subsequence)问题, 简称为LCS

说明: 这是一个非常有名的题目, 而且是一个分支中的主要问题, 这个分支称为字符串匹配
(String Matching), 可以说是计算机科学研究领域中比较早开发的科目, 目前的应用很广, 从语音分析到生化都能看到这一支的踪迹, 参看下面参考文献中各篇文章的介绍. 写程序的熟手或了解算法理论的朋友是不难写这个程序的, 因为它不过是一个动态规划(Dynamic Programming)的应用而已。给一点提示, 如果两个字符串是A=a[1]a[2]…a[m], B=b[1]b[2]…b[n],考虑a[i]与b[j]

如果在a[1]a[2]…a[i-1]与b[1]b[2]…b[j-1]这两个字符串的前段中已经找到了一个长度是k的公共子序列, 那么会有两种可能:

1. 如果a[i] = b[j], 于是把原来长度为k的共同部分序列后面补上ai, 就会得到a[1]a[2]…a[i]与b[1]b[2]…b[j]的一个长度是k+1的公共子序列
2. 如果a[i] != b[j],分成两种情况讨论: 第一, 检查a[1]a[2]…a[i-1]与b[1]…b[j-1]b[j]的最长公共子序列的长度; 第二, 检查a[1]…a[i-1]a[i]与b[1]b[2]…b[j-1]的最长共同部分序列的长度。最后进行适当的处理。

有了这个观点在心中, 找出最长公共子序列应该不会十分困难, 但是要如何把那个序列找出来呢? 这或许要好好想一想。

下面推荐的这本书是论文集有许许多与编修字符串方面的文章可供参考, 自然也包含有最长共同序列这个问题:此外,书中还有不少这些方面的应用与说明。

R.A. Wagner and M.J. Fischer. The String-to-String Correction Problem, Joumal of ACM。Vol.21(1974) p168~173

解答见longest_common_subsequence.py