Python求最长公共子串,可以使用动态规划的方法来求解。动态规划的步骤如下:
Python求最长公共子串,可以使用动态规划的方法来求解。
动态规划的步骤如下:
1. 定义状态:定义dp[i][j]表示字符串s1[0..i]和s2[0..j]的最长公共子串的长度。
2. 状态转移方程:当s1[i] == s2[j]时,dp[i][j] = dp[i-1][j-1] + 1;否则,dp[i][j] = 0。
3. 初始状态:dp[0][0] = 0,dp[i][0] = 0,dp[0][j] = 0(i > 0, j > 0)
4. 返回结果:max(dp[i][j]),即所有dp[i][j]中的最大值。
以下是Python代码实现:
def longestCommonSubstring(s1, s2):
m, n = len(s1), len(s2)
dp = [[0] * (n + 1) for _ in range(m + 1)]
res = 0
for i in range(1, m + 1):
for j in range(1, n + 1):
if s1[i - 1] == s2[j - 1]:
dp[i][j] = dp[i - 1][j - 1] + 1
res = max(res, dp[i][j])
return res
s1 = "abcde"
s2 = "abcef"
print(longestCommonSubstring(s1, s2)) # 4
本站系公益性非盈利分享网址,本文来自用户投稿,不代表码文网立场,如若转载,请注明出处
评论列表(34条)