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尋找最長公共子串算法的方法有哪些”的學習就結束了，希望能夠解決大家的疑惑。理論與實踐的搭配能更好的幫助大家學習，快去試試吧！若想繼續學習更多相關知識，請繼續關注億速云網站，小編會繼續努力為大家帶來更多實用的文章！