程序员面试题精选100题(20)-最长公共子串[算法]

时间:2019-09-22 编辑:9码倍投会不会死亭
题目:如果字符串一的所有字符按其在字符串中的顺序出现在另外一个字符串二中,则字符串一称之为字符串二的子串。注意,并不要求子串(字符串一)的字符必须连续出现在字符串二中。请编写一个函数,输入两个字符串,求它们的最长公共子串,并打印出最长公共子串。

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

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

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

先介绍LCS问题的性质:记Xm={x0, x1,…xm-1}Yn={y0,y1,…,yn-1}为两个字符串,而Zk={z0,z1,…zk-1}是它们的LCS,则:

1.???????如果xm-1=yn-1,那么zk-1=xm-1=yn-1,并且Zk-1Xm-1Yn-1LCS
2.???????如果xm-1≠yn-1,那么当zk-1≠xm-1ZXm-1YLCS
3.???????如果xm-1≠yn-1,那么当zk-1≠yn-1ZYn-1XLCS

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

1.???????如果zk-1≠xm-1,那么我们可以把xm-1yn-1)加到Z中得到Z’,这样就得到XY的一个长度为k+1的公共子串Z’。这就与长度为kZXYLCS相矛盾了。因此一定有zk-1=xm-1=yn-1

既然zk-1=xm-1=yn-1,那如果我们删除zk-1xm-1yn-1)得到的Zk-1Xm-1Yn-1,显然Zk-1Xm-1Yn-1的一个公共子串,现在我们证明Zk-1Xm-1Yn-1LCS。用反证法不难证明。假设有Xm-1Yn-1有一个长度超过k-1的公共子串W,那么我们把加到W中得到W’,那W’就是XY的公共子串,并且长度超过k,这就和已知条件相矛盾了。

2.???????还是用反证法证明。假设Z不是Xm-1YLCS,则存在一个长度超过kWXm-1YLCS,那W肯定也XY的公共子串,而已知条件中XY的公共子串的最大长度为k。矛盾。

3.???????证明同2

有了上面的性质,我们可以得出如下的思路:求两字符串Xm={x0, x1,…xm-1}Yn={y0,y1,…,yn-1}LCS,如果xm-1=yn-1,那么只需求得Xm-1Yn-1LCS,并在其后添加xm-1yn-1)即可;如果xm-1≠yn-1

本文已影响
相关文章