python解决最长公共子串和最长公共子序列

导读:本篇文章讲解 python解决最长公共子串和最长公共子序列,希望对大家有帮助,欢迎收藏,转发!站点地址:www.bmabk.com

  • 什么是最长公共子串??🤔
    最长公共子串就是指两个字符串中有部分子串相同且是最长的那个,例如,“abcdef” 和 “fgbcda” 的 最长公共子串就是 “bcd”。
  • 什么是最长公共子序列??🤔
    先来了解一下是什么是子序列,在数学应用中,某个序列的子序列就是从最初的序列通过去除某些元素但不破坏余下元素的相对位置(在前或者在后) 而形成的新序列。假设序列 “abcde” ,如果找到一个子序列可以是 “abc”、“ace”、或 “be”,但不可以是 “cae”。所以说如果求列表A和列表B的最长公共子序列,就是说既是A的额子序列又是B的子序列,而且要保证最长。

这两个问题都可以用二维的列表来解决

一、求最长公共子串长度

分别将两个要处理的字符串进行行和列上的二维化,把两两字母的比较结果映射到二维列表中。画出如下表格,分别对每个字母进行比较,处理方法如下图中所示:
在这里插入图片描述

str_a = 'hish'
str_b = 'fish'
cell = [[0 for j in range(len(str_a)+1)] for i in range(len(str_b)+1)]
#print(cell)
for j in range(1,len(str_a)+1):
    for i in range(1,len(str_b)+1):
        if str_a[j-1]==str_b[i-1]:
            cell[i][j] = cell[i-1][j-1]+1
        # else:
        #     cell[i][j] = 0
#print(cell)
maxList = []
for li in cell:
    maxList.append(max(li))
print(max(maxList))

二、求最长公共子序列长度

处理方式和上面类似,也是采用二维列表实现。
在这里插入图片描述

str_a = 'fosh'
str_b = 'fish'
cell = [[0 for j in range(len(str_a)+1)] for i in range(len(str_b)+1)]

for j in range(1,len(str_a)+1):
    for i in range(1,len(str_b)+1):
        if str_a[j-1]==str_b[i-1]:
            cell[i][j] = cell[i-1][j-1]+1
        else:
            cell[i][j] = max(cell[i-1][j],cell[i][j-1])
max_List = []
for li in cell:
    max_List.append(max(li))
print(max(max_List))

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

文章由半码博客整理,本文链接:https://www.bmabk.com/index.php/post/74934.html

(0)

相关推荐

半码博客——专业性很强的中文编程技术网站,欢迎收藏到浏览器,订阅我们!