圆月山庄资源网 Design By www.vgjia.com
最长公共子串(The Longest Common Substring)
LCS问题就是求两个字符串最长公共子串的问题。解法就是用一个矩阵来记录两个字符串中所有位置的两个字符之间的匹配情况,若是匹配则为1,否则为0。然后求出对角线最长的1的序列,其对应的位置就是最长匹配子串的位置。
def find_lcsubstr(s1, s2): m=[[0 for i in range(len(s2)+1)] for j in range(len(s1)+1)] #生成0矩阵,为方便后续计算,比字符串长度多了一列 mmax=0 #最长匹配的长度 p=0 #最长匹配对应在s1中的最后一位 for i in range(len(s1)): for j in range(len(s2)): if s1[i]==s2[j]: m[i+1][j+1]=m[i][j]+1 if m[i+1][j+1]>mmax: mmax=m[i+1][j+1] p=i+1 return s1[p-mmax:p],mmax #返回最长子串及其长度 print find_lcsubstr('abcdfg','abdfg')
运行得到输出:('dfg',3)
最长公共子序列 (The Longest Common Subsequence)
子串要求字符必须是连续的,但是子序列就不是这样。最长公共子序列是一个十分实用的问题,它可以描述两段文字之间的“相似度”,即它们的雷同程度,从而能够用来辨别抄袭。对一段文字进行修改之后,计算改动前后文字的最长公共子序列,将除此子序列外的部分提取出来,这种方法判断修改的部分,往往十分准确。
解法就是用动态回归的思想,一个矩阵记录两个字符串中匹配情况,若是匹配则为左上方的值加1,否则为左方和上方的最大值。一个矩阵记录转移方向,然后根据转移方向,回溯找到最长子序列。
import numpy def find_lcseque(s1, s2): # 生成字符串长度加1的0矩阵,m用来保存对应位置匹配的结果 m = [ [ 0 for x in range(len(s2)+1) ] for y in range(len(s1)+1) ] # d用来记录转移方向 d = [ [ None for x in range(len(s2)+1) ] for y in range(len(s1)+1) ] for p1 in range(len(s1)): for p2 in range(len(s2)): if s1[p1] == s2[p2]: #字符匹配成功,则该位置的值为左上方的值加1 m[p1+1][p2+1] = m[p1][p2]+1 d[p1+1][p2+1] = 'ok' elif m[p1+1][p2] > m[p1][p2+1]: #左值大于上值,则该位置的值为左值,并标记回溯时的方向 m[p1+1][p2+1] = m[p1+1][p2] d[p1+1][p2+1] = 'left' else: #上值大于左值,则该位置的值为上值,并标记方向up m[p1+1][p2+1] = m[p1][p2+1] d[p1+1][p2+1] = 'up' (p1, p2) = (len(s1), len(s2)) print numpy.array(d) s = [] while m[p1][p2]: #不为None时 c = d[p1][p2] if c == 'ok': #匹配成功,插入该字符,并向左上角找下一个 s.append(s1[p1-1]) p1-=1 p2-=1 if c =='left': #根据标记,向左找下一个 p2 -= 1 if c == 'up': #根据标记,向上找下一个 p1 -= 1 s.reverse() return ''.join(s) print find_lcseque('abdfg','abcdfg')
得到输出结果:
以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持。
圆月山庄资源网 Design By www.vgjia.com
广告合作:本站广告合作请联系QQ:858582 申请时备注:广告合作(否则不回)
免责声明:本站文章均来自网站采集或用户投稿,网站不提供任何软件下载或自行开发的软件! 如有用户或公司发现本站内容信息存在侵权行为,请邮件告知! 858582#qq.com
免责声明:本站文章均来自网站采集或用户投稿,网站不提供任何软件下载或自行开发的软件! 如有用户或公司发现本站内容信息存在侵权行为,请邮件告知! 858582#qq.com
圆月山庄资源网 Design By www.vgjia.com
暂无评论...
稳了!魔兽国服回归的3条重磅消息!官宣时间再确认!
昨天有一位朋友在大神群里分享,自己亚服账号被封号之后居然弹出了国服的封号信息对话框。
这里面让他访问的是一个国服的战网网址,com.cn和后面的zh都非常明白地表明这就是国服战网。
而他在复制这个网址并且进行登录之后,确实是网易的网址,也就是我们熟悉的停服之后国服发布的暴雪游戏产品运营到期开放退款的说明。这是一件比较奇怪的事情,因为以前都没有出现这样的情况,现在突然提示跳转到国服战网的网址,是不是说明了简体中文客户端已经开始进行更新了呢?
更新日志
2024年12月24日
2024年12月24日
- 小骆驼-《草原狼2(蓝光CD)》[原抓WAV+CUE]
- 群星《欢迎来到我身边 电影原声专辑》[320K/MP3][105.02MB]
- 群星《欢迎来到我身边 电影原声专辑》[FLAC/分轨][480.9MB]
- 雷婷《梦里蓝天HQⅡ》 2023头版限量编号低速原抓[WAV+CUE][463M]
- 群星《2024好听新歌42》AI调整音效【WAV分轨】
- 王思雨-《思念陪着鸿雁飞》WAV
- 王思雨《喜马拉雅HQ》头版限量编号[WAV+CUE]
- 李健《无时无刻》[WAV+CUE][590M]
- 陈奕迅《酝酿》[WAV分轨][502M]
- 卓依婷《化蝶》2CD[WAV+CUE][1.1G]
- 群星《吉他王(黑胶CD)》[WAV+CUE]
- 齐秦《穿乐(穿越)》[WAV+CUE]
- 发烧珍品《数位CD音响测试-动向效果(九)》【WAV+CUE】
- 邝美云《邝美云精装歌集》[DSF][1.6G]
- 吕方《爱一回伤一回》[WAV+CUE][454M]