提供网站建设备案,怀化网站优化哪个好,wordpress如何上传ppt,南昌医院网站建设最长公共子串公共子串问题费曼算法动态规划算法思路代码实现公共子串问题
在计算机科学中#xff0c;最长公共子串问题是寻找两个或多个已知字符串最长的子串。此问题与最长公共子序列问题的区别在于子序列不必是连续的#xff0c;而子串却必须是。链接: 百度百科
费曼算法…
最长公共子串公共子串问题费曼算法动态规划算法思路代码实现公共子串问题
在计算机科学中最长公共子串问题是寻找两个或多个已知字符串最长的子串。此问题与最长公共子序列问题的区别在于子序列不必是连续的而子串却必须是。链接: 百度百科
费曼算法
The Feynman Algorithm:
Write down the problem.Think real hard.Write down the solution.
动态规划算法思路 给定两个字符串T1和T2, 假设dp(i, j)表示T1T2在位置i, j的公共子串的长度【向位置0的方向连续相同的字符的数量】 比如“abcdefg”, “absecde” dp(0,0) 1 ‘a’ ‘a’ dp(1,1) 2 ‘ab’ ‘ab’ dp(1,2) 0 ‘b’ ! ‘s’ 总结规律 if T1[i] T2[j] : dp(i,j) dp(i-1,j-1) 1 else: dp(i,j) 0
代码实现 def getLcs(t1:str, t2:str)-str:get the longest common substring of two given stringif not t1:return t1if not t2:return t2# dp [[0 for i in range(len(t2)1)] for j in range(len(t1)1)]max_len 0dp [[0 for i in range(len(t2)1)] for j in range(2)]for i in range(1, len(t1)1):ind [0,1][i%20]for j in range(1, len(t2)1):if t1[i-1]t2[j-1]:dp[ind][j] dp[1-ind][j-1] 1else:dp[ind][j] 0if dp[ind][j] max_len:max_len dp[ind][j]p iprint(max_len:%d , pos: %d%(max_len,p))return t1[p-max_len:p]
