编程沙龙（11）
IT商界
对于任意两个字符串s1和s2(字符串中字符只限于26个小写的英文字母)的最长公共子序列lcs(s1,s2)是s1和s2中都出现的最长子序列。例如，tie是striped和tiger的最长公共子序列。
要求写一个程序，用户输入s1和s2，计算并显示出它们的最长公共子序列lcs(s1,s2)。
1.还是有一些朋友不是很理解题目的意思。例如有朋友问“striped和tiger的最长公共子序列为tie，为什么“r”不是公共子序列？？？”
这里我们要提出“序”的概念。我们不是找公共字符集，而是公共的子序列。“tiger”中“ie”在“r”的前面，而“striped”中“ie”在“r”的后面，所以顺序是不一样的。
2.有朋友问“如果最长子序列不止一个怎么办？”
这里我们对是否要找到所有的最长子序列没有做要求，只要你找到一个最长子序列就可以了。当然你可以做得更完美，这样你获奖的几率就会大增！
3.上期我们提供了一份有问题的程序源码，不知道朋友们有没有找出其中存在的问题。如果你还没有发现其中的问题，或者你自己就是这么想的，那也没关系，任何人不可能永远都对嘛。
下面我来分析一下这段程序。首先肯定的是这段程序是能找到两个字符串的公共子串的，但是不是就是最长的呢？比如说有两个子串s1=“bastr”、s2=“asbtrk”。按照上期的程序，因为s1比s2短，就以s1为基准来搜索s2。s1的首字符“b”是s2中第3个字符，这样就找到了第一个字符“b”，接着s1中的第二个字符“a”，要从s2的第4个字符“t”开始往后查找……这样我们得到的最长公共子串就是“btr”。这个答案看上去好像正确，其实是有问题的！“astr”应该也是s1、s2的公共子串，而且它的长度是4，它才应该是名副其实的最长公共子串。那么问题究竟出在哪里呢？根据上面的例子来看，坏就坏在这个“b”上了！它在s1、s2中都出现了，因为最先找到了它，结果就把“as”给跳过了。看到这儿，反应快的朋友可能会说：“如果是以s2为基准来搜索s1不就对了吗？”不错，应该是对的。那么是不是把上面的程序改一下，先是以s1为基准搜索s2，再以s2为基准搜索s1，最后比较两次找出的公共子串，长的那个就是最长公共子串了！看上去好像这个说法很完美了，至少应付上面的例子是绰绰有余了。那么先不要往下看，给你五分钟考虑一下，究竟对不对呢？
(五分钟倒计时中……)
我们还是用事实说话吧！再来看一个例子s1=“basdtr”、s2=“dasbtr”。按照上面的说法，我们找到了两个公共子串“btr”和“dtr”。好像问题又出现了，“astr”还是没被找出来！我最讨厌这种事情发生，解决了一个问题，又来一个！我们是应该停下来想想了。一可能是我们刚开始的方向就错了，二就是继续下去总会有找不出问题的时候。呵呵，现在该怎么办呢？我不能再说下去了，再说就是揭晓答案的时候了。朋友们可以用一个星期的时间来思考一下，下个星期公布答案！