最长子串_子串资源-CSDN文库

49 浏览量 2020-12-21 02:28:30 上传评论收藏 226KB PDF 举报

资源详情

资源评论

资源推荐

最长子串最长子串

最长子串最长子串

今天被小伙伴问到最长子串的东西，注意哦，它这里是要求连续的哦，和我之前的最长公共子序列有些不一样，但是捏，大同小异啦今天被小伙伴问到最长子串的东西，注意哦，它这里是要求连续的哦，和我之前的最长公共子序列有些不一样，但是捏，大同小异啦最长公共子

序列

这次这位小伙伴问的是这次这位小伙伴问的是python的，那我就用的，那我就用python做一下吧做一下吧（太久没写，真的缩进都看瞎了）

这里先上一种直接查找的方法，无需什么技术含量这里先上一种直接查找的方法，无需什么技术含量

把图画出来就一清二楚了

#直接查找

s1='abcdefgcpppppg加油denf'

s2='denf加油abcdppdenfcpppppp'

import re

def find_str(s1,s2):

if len(s1)>len(s2):

s1,s2=s2,s1 #保证s1小一点

length=len(s1)

result=[]#存储符合的结果

for i in range(length,0,-1):#后面开始遍历看，每次比较字符的数目

for j in range(0,length-i+1):

judge=False

tmp=s1[j:j+i] if s2.find(tmp)!=-1:#成功找到

result.append(tmp)

judge=True

new1=j+1

while judge:#看看有没有一样长的串

#这里要提醒一下，我们是从s1后面开始的，所以第一次找到就是最长的了

if new1+i>length:

break

newtmp=s1[new1:new1+i] if s2.find(newtmp)!=-1:

result.append(newtmp)

new1+=1

return result

print(find_str(s1,s2))

当然，我们还是要搞点技术活，我们用动态规划解决这个问题当然，我们还是要搞点技术活，我们用动态规划解决这个问题

按照我们之前说过的思路按照我们之前说过的思路

**1.子问题和状态设立：

我们考虑M（i，j）s1的第i个元素结尾，s2的第二个元素结尾的最长字串考虑就OK了

**

下面一张图就说明情况下面一张图就说明情况

这里我还是用python来呈现吧

word_a = "abcdefgcpppppg加油denf"

word_b = "denf加油abcdppdenfcpppppp"

def LEstring(string1,string2):

len1 = len(string1)

len2 = len(string2)

res = [[0 for i in range(len1+1)] for j in range(len2+1)] result = 0

for i in range(1,len2+1):

for j in range(1,len1+1):

if string2[i-1] == string1[j-1]:

res[i][j] = res[i-1][j-1]+1

result = max(map(max,res))

return result

print(LEstring(word_a,word_b))

#我只是输出个数，至于输出字符可以自己再遍历数组完成输出

学会程序和算法，走遍天下都不怕学会程序和算法，走遍天下都不怕

本内容试读结束，登录后可阅读更多

下载后可阅读完整内容，剩余1页未读，立即下载

评论0

内容反馈

weixin_38707342

粉丝: 7
资源: 925

最新资源

资源上传下载、课程学习等过程中有任何疑问或建议，欢迎提出宝贵意见哦~我们会及时处理！点击此处反馈

feedback-tip