最长公共子串 (Longest Common Substring)

题目描述:

给定两个字符串 A 和 B，找出它们的最长公共子串的长度。子串是指字符串中连续的一部分。

输入:

• A: 字符串 (1 <= A.length <= 1000)
• B: 字符串 (1 <= B.length <= 1000)

输出:

• 整数: 最长公共子串的长度

解题思路:

使用动态规划来解决此问题。定义一个二维数组 dp，其中 dp[i][j] 表示以 A[i-1] 和 B[j-1] 结尾的最长公共子串的长度。

状态转移方程:

• 如果 A[i-1] == B[j-1]，则 dp[i][j] = dp[i-1][j-1] + 1
• 否则，dp[i][j] = 0

边界条件:

• 初始时，dp[i][j] = 0（如果 i 或 j 为 0）
• 测试数据:

• 输入数据

• abcdef
• zcdemf

• 输出数据

• 3