解题思路

这是典型的字符串动态规划问题。设 str1 长度为 n，str2 长度为 m，我们用最长公共后缀的思想做 动态规划（DP）：

• 定义：dp[j] 表示在当前处理到 str1 的第 i 个字符、str2 的第 j 个字符时（均为下标从 1 开始），两者以这两个位置结尾的最长公共子串长度。

• 转移：

  • 若 str1[i-1] == str2[j-1]，则 dp[j] = dp[j-1] + 1；
  • 否则 dp[j] = 0（以当前两个位置结尾的公共子串被中断）。

• 为了做到空间复杂度 O(m)，我们用一维滚动数组并让 j 从右往左遍历，这样 dp[j-1] 仍是上一行（上一轮 i-1）的值。

题目内容

给定两个字符串 $str1$ 和 $str2$ ,输出两个字符串的最长公共子串题目保证 $str1$ 和 $str2$ 的最长公共子串存在且唯一。

数据范围：$1≤|strl|,|str2|< 5000$

要求：空间复杂度 $O(n)$，时间复杂度 $O(n*m)$

样例1

输入

"1AB2345CD","12345EF"

输出

"2345"