雅虎笔试题目：寻找最大公共子串

"雅虎笔试题目包含解答，主要涉及字符串处理和算法问题，如查找最大公共子串" 在雅虎的笔试题目中，有一道问题是寻找两个字符串的最大公共子串。这个问题在计算机科学和编程中是非常常见的，特别是在字符串处理和算法设计中。这里给出了两种不同的解法。 **解法一：滑动窗口法** 这个方法首先尝试直接在较长的字符串中查找较短的字符串，如果找到就直接返回。如果没有找到，它会通过滑动窗口的方式逐个字符地缩短较短的字符串，检查是否为较长字符串的子串。这种方法使用了`strstr()`函数来检查子串是否存在。代码中定义了一个名为`commanstring`的函数，它接受两个字符串参数，并返回它们的最大公共子串。在主函数`main`中，通过输入两个字符串，然后调用`commanstring`函数，最后输出结果。 **解法二：动态规划法** 这种方法利用了动态规划的思想，构建一个m×n的矩阵，其中m和n分别是两个字符串的长度。矩阵的每个元素表示对应位置的字符是否相等。如果相等，值为1，否则为0。然后寻找最长的连续1的对角线，其长度即为最大公共子串的长度。为了优化空间复杂度，可以不实际创建矩阵，只保留一个长度为m的一维数组，根据前一行的状态更新当前行，这样只需要O(m)的空间。 在动态规划的实现中，定义一个一维数组`c`，其长度等于较短字符串的长度。如果当前位置的字符匹配，`c[j][i]`的值等于`c[j-1][i-1]+1`，否则`c[j][i]`保持为0。这种方法的关键在于，当前状态只与前一行的状态有关，所以可以避免存储整个矩阵，从而降低空间复杂度。 这两种方法各有优缺点。滑动窗口法简单直观，但可能需要遍历多次；动态规划法虽然需要更多的逻辑处理，但空间效率更高。在实际应用中，应根据问题规模和资源限制选择合适的方法。在面试或笔试中，理解并能正确实现这两种方法都是展示编程能力的重要方面。