python寻找最长公共子串算法的方法有哪些

这篇文章主要介绍“python寻找最长公共子串算法的方法有哪些”，在日常操作中，相信很多人在python寻找最长公共子串算法的方法有哪些问题上存在疑惑，小编查阅了各式资料，整理出简单好用的操作方法，希望对大家解答”python寻找最长公共子串算法的方法有哪些”的疑惑有所帮助！接下来，请跟着小编一起来学习吧！

算法题：

找出两个字符串的最长公共子串！

分析题目：

2个字符串中可能存在多个相同长度的最长公共子串，所以返回的应该是列表。

双循环遍历二个子串，找到重复的子串将其添加入最长子串列表，同时记录最长子串长度。循环中遇到更长的子串时将其添加入最长子串列表，同时修正最长子串长度。

简洁代码：

def find_repeat1(a, b):longest = []  # 最长子串仓库max = 0  # 最长子串长度for x in range(len(b)):  # x是字符串b的指针y = 0  # y是字符串a的指针while y < len(a):long = ''  # 子串申明z = 0  # 子串长度# 判断若a子串指针和b子串指针都不越界且它们指向的字符相同则进入循环while y+z < len(a) and x+z < len(b) and a[y+z] == b[x+z]: long += a[y + z]  # 子串累加z += 1  # 子串长度累加if z >= max:  # 子串长度超过最长子串长度longest.append(long)  # 将该子串加入仓库max = z  # 最长子串长度修正y = y + z if z > 0 else y + 1  # 修正字符串b的指针longest = set(longest)  # 去重return [i for i in longest if len(i) == max]  # 返回所有符合最长长度的子串

简洁风代码有17行。

实用代码：

def find_repeat2(a, b):longest = []  # 保存有重复的子串lena = len(a)lenb = len(b)max = 0  # 最长长度for x in range(lenb):  # x是字符串b的指针y = 0  # y是字符串a的指针for y in range(lena):if a[y] == b[x]:  # 判断字符是否相同long = ''  # 临时子串z = 0  # 统计子串长度keya = y  # 记录a开始重复的位置keyb = x  # 记录b开始重复的位置while a[keya] == b[keyb]:long += a[keya]  # 有重复的那么子串累加z += 1  # 子串长度累加keya += 1  # a开始重复的位置指针+1keyb += 1  # b开始重复的位置指针+1if keya >= lena or keyb >= lenb:  #如果a或b指针越界break  # 退出循环if z >= max:  # 临时子串长度大于最大长度max = z  # 最大长度修正longest.append(long)  # 将临时子串添加入库longest = set(longest)  # 去重return [i for i in longest if len(i) == max]  # 返回所有符合最长长度的子串

实用风代码有25行。

代码比较：

简洁风代码比实用风代码少了三分之一，很大的差距了。现在我们来比较一下它们的性能。为了测试性能，我传入2个超长的字符串来作比较：

a = 'abdomen' * 300b = 'dfomenshfabdomh' * 300t1 = time.time()print(find_repeat1(a, b))t2 = time.time()print(t2 - t1)print('=' * 20)t1 = time.time()print(find_repeat2(a, b))t2 = time.time()print(t2 - t1)print(17 / 25)print(t3 / t4)print('=' * 20)out:['abdom']5.348941802978516====================['abdom']1.5207555294036865====================0.683.4231525397933256

简洁代码长度只有实用代码长度的68%，简洁代码耗时是实用代码的3.4倍！！！

2种代码核心算法完全一致，性能却差了这么多！！！

到此，关于“python寻找最长公共子串算法的方法有哪些”的学习就结束了，希望能够解决大家的疑惑。理论与实践的搭配能更好的帮助大家学习，快去试试吧！若想继续学习更多相关知识，请继续关注亿速云网站，小编会继续努力为大家带来更多实用的文章！