python實(shí)現(xiàn)求兩個字符串的最長公共子串方法
更新時間：2018年07月20日 09:21:43 作者：chimuuu
今天小編就為大家分享一篇python實(shí)現(xiàn)求兩個字符串的最長公共子串方法，具有很好的參考價值，希望對大家有所幫助。一起跟隨小編過來看看吧
如下所示：
# coding:utf-8
'''
求兩個字符串的最長公共子串
思想：建立一個二維數(shù)組，保存連續(xù)位相同與否的狀態(tài)
'''
def getNumofCommonSubstr(str1, str2):
lstr1 = len(str1)
lstr2 = len(str2)
record = [[0 for i in range(lstr2+1)] for j in range(lstr1+1)] # 多一位
maxNum = 0 # 最長匹配長度
p = 0 # 匹配的起始位
for i in range(lstr1):
for j in range(lstr2):
if str1[i] == str2[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 + 1
return str1[p-maxNum:p], maxNum
if __name__ == '__main__':
str1 = raw_input()
str2 = raw_input()
res = getNumofCommonSubstr(str1, str2)
print res
輸出結(jié)果：字符串str1中的第一個最長公共子串（若有重復(fù)）
以上這篇python實(shí)現(xiàn)求兩個字符串的最長公共子串方法就是小編分享給大家的全部內(nèi)容了，希望能給大家一個參考，也希望大家多多支持腳本之家。
相關(guān)文章
這篇文章主要介紹了用python找出那些被“標(biāo)記”的照片的相關(guān)資料,需要的朋友可以參考下2017-04-04
reportlab是Python的一個標(biāo)準(zhǔn)庫，可以畫圖、畫表格、編輯文字，最后可以輸出PDF格式。本文將利用reportlab模塊生成圖文并茂的PDF報告，感興趣的可以了解一下2022-06-06
二叉樹是一種特殊的樹,最直觀地體現(xiàn)于它的每個節(jié)點(diǎn)至多有兩個子節(jié)點(diǎn),二叉樹是非常實(shí)用的一種數(shù)據(jù)結(jié)構(gòu),常常用于實(shí)現(xiàn)二叉查找樹及二叉堆等,下面這篇文章主要給大家介紹了關(guān)于python二叉樹類以及其4種遍歷方法的相關(guān)資料,需要的朋友可以參考下2022-05-05
python 限制函數(shù)調(diào)用次數(shù)的實(shí)例講解
下面小編就為大家分享一篇python 限制函數(shù)調(diào)用次數(shù)的實(shí)例講解，具有很好的參考價值，希望對大家有所幫助。一起跟隨小編過來看看吧2018-04-04
這篇文章主要介紹了python實(shí)現(xiàn)文法左遞歸的消除的方法，本文通過實(shí)例代碼給大家介紹的非常詳細(xì)，對大家的學(xué)習(xí)或工作具有一定的參考借鑒價值,需要的朋友可以參考下2020-05-05
python+OpenCV人臉識別考勤系統(tǒng)實(shí)現(xiàn)的詳細(xì)代碼
作為一個基于人臉識別算法的考勤系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)教程，以下內(nèi)容將提供詳細(xì)的步驟和代碼示例。本教程將使用 Python 語言和 OpenCV 庫進(jìn)行實(shí)現(xiàn),需要的朋友可以參考下2023-05-05
flask使用session保存登錄狀態(tài)及攔截未登錄請求代碼
這篇文章主要介紹了flask使用session保存登錄狀態(tài)及攔截未登錄請求代碼，具有一定借鑒價值,需要的朋友可以參考下2018-01-01
利用python實(shí)現(xiàn)PSO算法優(yōu)化二元函數(shù)
這篇文章主要介紹了python實(shí)現(xiàn)PSO算法優(yōu)化二元函數(shù)的代碼，非常不錯，具有一定的參考借鑒價值,需要的朋友可以參考下2019-11-11
Python+matplotlib實(shí)現(xiàn)餅圖的繪制
Matplotlib是一個Python的2D繪圖庫，它以各種硬拷貝格式和跨平臺的交互式環(huán)境生成出版質(zhì)量級別的圖形。本文將利用Matplotlib庫繪制餅圖，感興趣的可以了解一下2022-03-03
Pytorch數(shù)據(jù)拼接與拆分操作實(shí)現(xiàn)圖解
這篇文章主要介紹了Pytorch數(shù)據(jù)拼接與拆分操作實(shí)現(xiàn)圖解,文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值,需要的朋友可以參考下2020-04-04