动态规划--最长公共子串
创始人
2024-05-27 18:35:54
0次

最长公共子串

  • 公共子串问题
  • 费曼算法
  • 动态规划算法思路
    • 代码实现

公共子串问题

在计算机科学中，最长公共子串问题是寻找两个或多个已知字符串最长的子串。此问题与最长公共子序列问题的区别在于子序列不必是连续的，而子串却必须是。链接: 百度百科

费曼算法

The Feynman Algorithm:

  1. Write down the problem.
  2. Think real hard.
  3. Write down the solution.

动态规划算法思路

  1. 给定两个字符串T1和T2, 假设dp(i, j)表示T1，T2在位置i, j的公共子串的长度【向位置0的方向，连续相同的字符的数量】
    比如“abcdefg”, “absecde”
    dp(0,0) = 1 ‘a’ == ‘a’
    dp(1,1) = 2 ‘ab’ == ‘ab’
    dp(1,2) = 0 ‘b’ != ‘s’

  2. 总结规律：
    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 string'''if 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%2==0]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]
词库加载错误:未能找到文件“E:\highferrum_mysql\Configuration\Dict_Stopwords.txt”。

上一篇：【洛谷 P2089】烤鸡（循环枚举）

下一篇：【Hello Linux】程序地址空间

相关内容

热门资讯

婚纱走秀主持词 婚纱走秀主持词三篇　　篇一：婚纱走秀演出主持词　　当您披上洁白的婚纱，点亮您一生中最美丽的日子，您是...
医者仁心台词 医者仁心台词大全　　1. 钟立行对丁祖望：我们都在努力做一个能够被人怀念的人。　　2.罗雪樱旁白：从...
《美丽人生》的经典台词 《美丽人生》的经典台词　　意大利电影《美丽人生》，由罗伯托贝尼尼自编自演，讲述了意大利一对犹太父子被...
二年级主持词 二年级主持词　　主持词分为会议主持词、晚会主持词、活动主持词、婚庆主持词等。在一步步向前发展的社会中...
年会的主持词 年会的主持词范文（通用5篇）　　根据活动对象的不同，需要设置不同的主持词。时代不断在进步，主持词是活...
姨妈的后现代生活经典台词分享 姨妈的后现代生活经典台词分享　　吉日良辰当欢笑，为什么鲛珠化泪抛?此时却又明白了，世上何尝尽富豪。也...
学校语文教研活动主持词 学校语文教研活动主持词　　借鉴诗词和散文诗是主持词的一种写作手法。在一步步向前发展的社会中，很多晚会...
六一庆祝大会主持词 六一庆祝大会主持词　　六一就是我们的节日，六一就是一个欢乐的日子，下面小编整理的六一庆祝大会主持词，...
婚礼感谢词 婚礼感谢词(15篇)婚礼感谢词1各位来宾，各位亲友:　　大家晚上好！　　今日是我女儿XXX和女婿XX...
文艺汇演主持词开场白 文艺汇演主持词开场白9篇　　根据活动对象的不同，需要设置不同的主持词。我们眼下的社会，活动集会越来越...
总结大会主持词 　　导语：春去秋回又一栽，似水流年旺年来。　　2017年公司年会主持词　　一.主持人开场白　　男：一...
农村结婚典礼主持词 农村结婚典礼主持词　　一对新人立堂前，两心相印似蜜甜，三生有幸结良缘，下面是小编分享的 农村结婚典礼...
春节联欢晚会主持词开场白 　　翻开精美的日历，我细数着春节将要来临。那是我们中华民族的传统节日，更是我期盼的佳节，因为只有这几...
真爱至上中英文经典台词 真爱至上中英文经典台词　　1、All I want for Christmas is you.　　今...
欢聚一堂舞蹈主持词 欢聚一堂舞蹈主持词　　串词是在晚会、联欢会等大型联欢活动中，主持人把前后节目，把整台节目恰到好处的联...
主持词结束语 主持词结束语（通用12篇）　　利用在中国拥有几千年文化的诗词能够有效提高主持词的感染力。在人们越来越...
秋季小学开学典礼校长的致辞 秋季小学开学典礼校长的致辞（通用13篇）　　在学习、工作、生活中，许多人都有过写致辞的经历，对致辞都...
五月的主持词开场白 五月的主持词开场白　　主持人在台上表演的灵魂就表现在主持词中。在当下这个社会中，各种场合中活跃现场气...
重阳节优秀致辞 重阳节优秀致辞范文　　无论是身处学校还是步入社会，大家都用到过致辞吧，在各种重大的庆典、外交、纪念活...
QQ群晚会开幕词 QQ群晚会开幕词　　QQ群晚会开幕词　　　　尊贵的各位嘉宾，群主，各位管理，群友们大家晚上好：　　　...