程序员面试题精选100题（20）－最长公共子串[算法]

例如：输入两个字符串BDCABA和ABCBDAB，字符串BCBA和BDAB都是是它们的最长公共子串，则输出它们的长度4，并打印任意一个子串。

分析：求最长公共子串（Longest Common Subsequence, LCS）是一道非常经典的动态规划题，因此一些重视算法的公司像MicroStrategy都把它当作面试题。

完整介绍动态规划将需要很长的篇幅，因此我不打算在此全面讨论动态规划相关的概念，只集中对LCS直接相关内容作讨论。如果对动态规划不是很熟悉，请参考相关算法书比如算法讨论。

先介绍LCS问题的性质：记X_m={x₀, x₁,…x_m-1}和Y_n={y₀,y₁,…,y_n-1}为两个字符串，而Z_k={z₀,z₁,…z_k-1}是它们的LCS，则：

1.       如果x_m-1=y_n-1，那么z_k-1=x_m-1=y_n-1，并且Z_k-1是X_m-1和Y_n-1的LCS；
2.       如果x_m-1≠y_n-1，那么当z_k-1≠x_m-1时Z是X_m-1和Y的LCS；
3.       如果x_m-1≠y_n-1，那么当z_k-1≠y_n-1时Z是Y_n-1和X的LCS；

下面简单证明一下这些性质：

1.       如果z_k-1≠x_m-1，那么我们可以把x_m-1（y_n-1）加到Z中得到Z’，这样就得到X和Y的一个长度为k+1的公共子串Z’。这就与长度为k的Z是X和Y的LCS相矛盾了。因此一定有z_k-1=x_m-1=y_n-1。

既然z_k-1=x_m-1=y_n-1，那如果我们删除z_k-1（x_m-1、y_n-1）得到的Z_k-1，X_m-1和Y_n-1，显然Z_k-1是X_m-1和Y_n-1的一个公共子串，现在我们证明Z_k-1是X_m-1和Y_n-1的LCS。用反证法不难证明。假设有X_m-1和Y_n-1有一个长度超过k-1的公共子串W，那么我们把加到W中得到W’，那W’就是X和Y的公共子串，并且长度超过k，这就和已知条件相矛盾了。

2.       还是用反证法证明。假设Z不是X_m-1和Y的LCS，则存在一个长度超过k的W是X_m-1和Y的LCS，那W肯定也X和Y的公共子串，而已知条件中X和Y的公共子串的最大长度为k。矛盾。

3.       证明同2。

有了上面的性质，我们可以得出如下的思路：求两字符串X_m={x₀, x₁,…x_m-1}和Y_n={y₀,y₁,…,y_n-1}的LCS，如果x_m-1=y_n-1，那么只需求得X_m-1和Y_n-1的LCS，并在其后添加x_m-1（y_n-1）即可；如果x_m-1≠y_n-1