python實(shí)現(xiàn)求兩個(gè)字符串的最長(zhǎng)公共子串方法

更新時(shí)間：2018年07月20日 09:21:43 作者：chimuuu

今天小編就為大家分享一篇python實(shí)現(xiàn)求兩個(gè)字符串的最長(zhǎng)公共子串方法，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。一起跟隨小編過來看看吧

如下所示：

# coding:utf-8
'''
求兩個(gè)字符串的最長(zhǎng)公共子串
思想：建立一個(gè)二維數(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   # 最長(zhǎng)匹配長(zhǎng)度
 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:
     # 獲取最大匹配長(zhǎng)度
     maxNum = record[i+1][j+1]
     # 記錄最大匹配長(zhǎng)度的終止位置
     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中的第一個(gè)最長(zhǎng)公共子串（若有重復(fù)）

以上這篇python實(shí)現(xiàn)求兩個(gè)字符串的最長(zhǎng)公共子串方法就是小編分享給大家的全部?jī)?nèi)容了，希望能給大家一個(gè)參考，也希望大家多多支持腳本之家。

您可能感興趣的文章:

相關(guān)文章

用python找出那些被“標(biāo)記”的照片
這篇文章主要介紹了用python找出那些被“標(biāo)記”的照片的相關(guān)資料,需要的朋友可以參考下
2017-04-04
Python生成圖文并茂的PDF報(bào)告的方法詳解
reportlab是Python的一個(gè)標(biāo)準(zhǔn)庫，可以畫圖、畫表格、編輯文字，最后可以輸出PDF格式。本文將利用reportlab模塊生成圖文并茂的PDF報(bào)告，感興趣的可以了解一下
2022-06-06
python二叉樹類以及其4種遍歷方法實(shí)例
二叉樹是一種特殊的樹,最直觀地體現(xiàn)于它的每個(gè)節(jié)點(diǎn)至多有兩個(gè)子節(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í)例講解，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。一起跟隨小編過來看看吧
2018-04-04
python實(shí)現(xiàn)文法左遞歸的消除方法
這篇文章主要介紹了python實(shí)現(xiàn)文法左遞歸的消除的方法，本文通過實(shí)例代碼給大家介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值,需要的朋友可以參考下
2020-05-05
python+OpenCV人臉識(shí)別考勤系統(tǒng)實(shí)現(xiàn)的詳細(xì)代碼
作為一個(gè)基于人臉識(shí)別算法的考勤系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)教程，以下內(nèi)容將提供詳細(xì)的步驟和代碼示例。本教程將使用 Python 語言和 OpenCV 庫進(jìn)行實(shí)現(xiàn),需要的朋友可以參考下
2023-05-05
flask使用session保存登錄狀態(tài)及攔截未登錄請(qǐng)求代碼
這篇文章主要介紹了flask使用session保存登錄狀態(tài)及攔截未登錄請(qǐng)求代碼，具有一定借鑒價(jià)值,需要的朋友可以參考下
2018-01-01
利用python實(shí)現(xiàn)PSO算法優(yōu)化二元函數(shù)
這篇文章主要介紹了python實(shí)現(xiàn)PSO算法優(yōu)化二元函數(shù)的代碼，非常不錯(cuò)，具有一定的參考借鑒價(jià)值,需要的朋友可以參考下
2019-11-11
Python+matplotlib實(shí)現(xiàn)餅圖的繪制
Matplotlib是一個(gè)Python的2D繪圖庫，它以各種硬拷貝格式和跨平臺(tái)的交互式環(huán)境生成出版質(zhì)量級(jí)別的圖形。本文將利用Matplotlib庫繪制餅圖，感興趣的可以了解一下
2022-03-03
Pytorch數(shù)據(jù)拼接與拆分操作實(shí)現(xiàn)圖解
這篇文章主要介紹了Pytorch數(shù)據(jù)拼接與拆分操作實(shí)現(xiàn)圖解,文中通過示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友可以參考下
2020-04-04