前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >[Python]获取2个字符串的最长公共子串

[Python]获取2个字符串的最长公共子串

作者头像
祥知道
发布2020-03-10 15:57:11
2.5K0
发布2020-03-10 15:57:11
举报
文章被收录于专栏:祥的专栏

原创文章,欢迎转载。转载请注明:转载自 祥的博客

原文链接:https://cloud.tencent.com/developer/article/1596385


文章目录

代码语言:txt
复制
- @[toc]1.问题引出源码及测试结果2.1. 程序源码2.2. 测试结果分析Next

1.问题引出

我下载了一些英语资料,这些资料的命名还好,但是就是没有用文件夹归档,整体感觉很乱,所以打算要将他们用文件夹分类。

计划是这样的:

  1. 查找所有pdfpdf名字创建文件夹,并将对应的pdf文件,移入文件夹中;
  2. 查找与pdf名字最接近的MP3文件,并将其移入对应的文件夹中。

看到明显是一本书的文本音频资料

  • 文本:黑猫英语名著3级 02 Alic's Adventures In Wonderland 艾丽丝漫游奇境记.pdf
  • 音频:艾丽丝漫游奇境记 Alic_s Adventures In Wonderland 01.mp3

可以发现,他们都有相同的子字符串 ,所以先要处理找两个字符串最长公共子串的问题

2. 源码及测试结果

2.1. 程序源码

代码语言:javascript
复制
def getMaxCommonSubstr(s1, s2):
# 求两个字符串的最长公共子串
# 思想:建立一个二维数组,保存连续位相同与否的状态

    len_s1 = len(s1)
    len_s2 = len(s2)

    # 生成0矩阵,为方便后续计算,多加了1行1列
    # 行: (len_s1+1)
    # 列: (len_s2+1)
    record = [[0 for i in range(len_s2+1)] for j in range(len_s1+1)]    
    
    maxNum = 0          # 最长匹配长度
    p = 0               # 字符串匹配的终止下标 

    for i in range(len_s1):
        for j in range(len_s2):
            if s1[i] == s2[j]:
                # 相同则累加
                record[i+1][j+1] = record[i][j] + 1
                
                if record[i+1][j+1] > maxNum:
                    maxNum = record[i+1][j+1]
                    p = i # 匹配到下标i

    # 返回 子串长度,子串
    return maxNum, s1[p+1-maxNum : p+1]



def printMatrixList(li):
# 打印多维list
    row = len(li)
    col = len(li[0])
    
    for i in range(row):
        for j in range(col):
            print(li[i][j], end=' ')
        print('')


    
    
if __name__ == "__main__":

    # s1="黑猫英语名著3级 02 Alic's Adventures In Wonderland 艾丽丝漫游奇境记.pdf"
    # s2="艾丽丝漫游奇境记 Alic_s Adventures In Wonderland 01.mp3"
    s1='abcdef'
    s2='bcxdef'
    [lenMatch,strMatch] = getMaxCommonSubstr(s1,s2)
    print('子串: ', strMatch)
    print('子串长度: ', lenMatch)

2.2. 测试结果

代码语言:javascript
复制
# 如果数据是`abcdef`等
子串:  def
子串长度:  3

# 如果数据是`艾丽丝`等
子串:  s Adventures In Wonderland
子串长度:  27

3. 分析

对于测试字符串为:

代码语言:javascript
复制
s1='abcdef'
s2='bcxdef'

明显看出有2个公共子串,bcdef,上述的方法就是用2个字符串各自的长度建立了一个矩阵,矩阵数值初始都是0,一个字符一个字符的进行对比,如果字符相等,就在左上对角线元素的数值上加一(如下面所示)。

假设字符串长度分别为nm,则创建这个矩阵的时候,算法复杂度为O(nm),查找最大子串的算法复杂度为O(nm),整体算法的复杂度为2O(nm)

理论上,可以把创建矩阵和查找放在一起,这样就会优化许多,等我闲了再搞吧,先完成主要目标。

代码语言:javascript
复制
0 b c x d e f
a 0 0 0 0 0 0
b 1 0 0 0 0 0
c 0 2 0 0 0 0
d 0 0 0 1 0 0
e 0 0 0 0 2 0
f 0 0 0 0 0 3

4. Next

最终不要忘了 初心

[Python]将MP3和PDF按名字分类归档到各自文件夹 : https://blog.csdn.net/humanking7/article/details/84663012


以上,Enjoy~

本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 文章目录
  • 1.问题引出
  • 2. 源码及测试结果
    • 2.1. 程序源码
      • 2.2. 测试结果
      • 3. 分析
      • 4. Next
      领券
      问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档