华科软院复试上机题：最长公共子串算法解析

"华科软院复试上机题.pdf" 这篇文档是华中科技大学软件学院复试上机考试的题目集，包含了对编程能力的考察，特别是动态规划算法的应用。其中一道具体的题目是寻找两个字符串的最长公共子串，并要求在输出时不包含空格。 题目描述： 该题目要求编写一个程序，计算并输出两个字符串的最长公共子串。最长公共子串是指在两个给定的字符串中都存在的最长连续子序列。程序需要处理长度不超过255的字符串，并且在输出时排除任何空格。 解题思路及算法分析： 1. 动态规划法（Dynamic Programming, DP）：这是解决这类问题的常用方法。创建一个二维数组dp[i][j]，其中dp[i][j]表示字符串str1的前i个字符与str2的前j个字符的最长公共子串的长度。 2. 初始化：当i=0或j=0时，两个字符串中没有共同的部分，所以dp[i][j]=0。 3. 更新dp数组：如果str1[i]等于str2[j]，那么dp[i][j]等于dp[i-1][j-1]加1（因为找到了一个共同的字符，公共子串长度增加1）。如果str1[i]不等于str2[j]，则dp[i][j]=0，表示没有公共子串。 4. 特殊处理：在处理字符串时，应忽略空格。在最后输出结果时，只需要输出不含空格的子串。 5. 记录最长子串结束位置：为了输出所有长度等于最大长度的公共子串，可以使用额外的数据结构（如数组endStr1[N]）来记录dp[i][j]==maxLen的子串的结束位置，然后遍历这些结束位置以输出所有最长公共子串。 6. 主函数实现：首先读取两个字符串，然后使用双重循环计算dp数组，同时更新maxLen。在循环结束后，遍历endStr1[N]，调用打印子串的辅助函数printSubstring()，将所有最长公共子串输出。 通过这个题目，考生可以复习和练习动态规划、字符串处理以及数组操作等C++编程基础，同时也需要对算法的时间复杂度和空间复杂度有所理解，以适应面试中可能的性能要求。