2015上半年程序员下午试卷：寻找最长公共子串

"该资源是一份2015年上半年程序员资格考试下午试卷的案例分析部分，主要考察的是程序设计和算法理解，特别是涉及到查找两个字符串之间的最长公共子串的问题。" 在计算机科学中，字符串处理是一项基本任务，而寻找两个字符串的最长公共子串是一个常见的算法问题。这个问题在文本比较、数据挖掘以及软件开发等多个领域都有应用。在这个案例中，题目给出的流程图是用来找出两个给定字符串A和B的最长公共子串的长度L以及它们在各自字符串中的起始位置。 首先，我们要理解算法的基本思路。由于字符串A的长度为M，字符串B的长度为N，且M≥N≥1，最长公共子串的长度L不会超过较小的字符串长度N。因此，算法从最大可能的公共子串长度L=N开始递减检查，直至找到一个实际存在的公共子串。 流程图的执行流程如下： 1. 初始化L为N或min(M,N)，因为最长公共子串的长度不能超过最小的字符串长度。 2. 对于每个可能的L值，我们需要在两个字符串中寻找长度为L的子串。对于字符串A，我们从下标1开始，直到M-L+1，每次增加1，取出一个长度为L的子串。对于字符串B，同样的操作，从下标1到N-L+1。 3. 在取出子串后，通过某种方法（此处省略的流程）判断这两个长度为L的子串是否完全相同。如果相同，则找到了一个长度为L的公共子串。 4. 这一过程会递减L并重复，直到找到最长的公共子串，或者L减至0，表示没有公共子串。 5. 当找到最长公共子串时，记录其长度L和在原字符串中的起始位置。 在编程实现这个算法时，通常会使用两个嵌套的循环，外层循环控制L的递减，内层循环用于在两个字符串中匹配长度为L的子串。这可以使用滑动窗口技术或者动态规划来实现。动态规划方法通常更高效，因为它避免了重复计算。 这个案例题考察了程序员对基础算法的理解和应用能力，以及对字符串处理的熟练程度。在实际编程工作中，这种问题解决技巧对于进行文本相似度计算、源代码比较等方面的工作非常重要。