Python實現(xiàn)針對給定字符串尋找最長非重復(fù)子串的方法
更新時間：2018年04月21日 11:37:46 作者：Together_CZ
這篇文章主要介紹了Python實現(xiàn)針對給定字符串尋找最長非重復(fù)子串的方法,涉及Python針對字符串的遍歷、排序、計算等相關(guān)操作技巧,需要的朋友可以參考下
本文實例講述了Python實現(xiàn)針對給定字符串尋找最長非重復(fù)子串的方法。分享給大家供大家參考，具體如下：
問題：
給定一個字符串，尋找其中最長的重復(fù)子序列，如果字符串是單個字符組成的話如“aaaaaaaaaaaaa”那么滿足要求的輸出就是a
思路：
這里的思路有兩種是我能想到的
（1）從頭開始遍歷字符串，設(shè)置標(biāo)志位，在往后走的過程中當(dāng)發(fā)現(xiàn)和之前標(biāo)志位重合的時候就回頭檢查一下這個新出現(xiàn)的子串是否跟前面字符串或者前面字符串的子串相同，相同則記錄該子串并計數(shù)加1，直至處理完畢
（2）利用滑窗切片的機(jī)制，生成所有的切片接下來統(tǒng)計和處理，主要利用到了兩次排序的功能
本文采用的是第二種方法，下面是具體實現(xiàn)：
#!usr/bin/env python
#encoding:utf-8
'''''
__Author__:沂水寒城
功能：給定一個字符串，尋找最長重復(fù)子串
'''
from collections import Counter
def slice_window(one_str,w=1):
'''''
滑窗函數(shù)
'''
res_list=[]
for i in range(0,len(one_str)-w+1):
res_list.append(one_str[i:i+w])
return res_list
def main_func(one_str):
'''''
主函數(shù)
'''
all_sub=[]
for i in range(1,len(one_str)):
all_sub+=slice_window(one_str,i)
res_dict={}
#print Counter(all_sub)
threshold=Counter(all_sub).most_common(1)[0][1]
slice_w=Counter(all_sub).most_common(1)[0][0]
for one in all_sub:
if one in res_dict:
res_dict[one]+=1
else:
res_dict[one]=1
sorted_list=sorted(res_dict.items(), key=lambda e:e[1], reverse=True)
tmp_list=[one for one in sorted_list if one[1]>=threshold]
tmp_list.sort(lambda x,y:cmp(len(x[0]),len(y[0])),reverse=True)
#print tmp_list
print tmp_list[0][0]
if __name__ == '__main__':
print "腳本之家測試結(jié)果："
one_str='abcabcd'
two_str='abcabcabd'
three_str='bbbbbbb'
main_func(one_str)
main_func(two_str)
main_func(three_str)
結(jié)果如下：
更多關(guān)于Python相關(guān)內(nèi)容可查看本站專題：《Python字符串操作技巧匯總》、《Python數(shù)據(jù)結(jié)構(gòu)與算法教程》、《Python函數(shù)使用技巧總結(jié)》、《Python入門與進(jìn)階經(jīng)典教程》及《Python文件與目錄操作技巧匯總》
希望本文所述對大家Python程序設(shè)計有所幫助。
相關(guān)文章
對Python3中bytes和HexStr之間的轉(zhuǎn)換詳解
今天小編就為大家分享一篇對Python3中bytes和HexStr之間的轉(zhuǎn)換詳解，具有很好的參考價值，希望對大家有所幫助。一起跟隨小編過來看看吧2018-12-12
這篇文章主要介紹了如何用 Python 制作地球儀，本文通過實例代碼給大家介紹的非常詳細(xì)，對大家的學(xué)習(xí)或工作具有一定的參考即將價值,需要的朋友可以參考下2020-04-04
這篇文章主要介紹了python多線程并發(fā)實例及其優(yōu)化,threading是擴(kuò)展模塊，在thread的基礎(chǔ)上進(jìn)行了封裝及改進(jìn)。所以只需要使用threading這個模塊就能完成并發(fā)的測試,需要的朋友可以參考下2019-06-06
Python NumPy數(shù)組裁切和數(shù)據(jù)類型的實現(xiàn)即原理詳解
這篇文章主要介紹了Python NumPy數(shù)組裁切和數(shù)據(jù)類型的實現(xiàn)即原理，文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值，需要的朋友們下面隨著小編來一起學(xué)習(xí)吧2023-05-05
你應(yīng)當(dāng)將下邊的例子運行多次，以便可以注意到線程是不可預(yù)測的和線程每次運行出的不同結(jié)果。聲明：從這里開始忘掉你聽到過的關(guān)于GIL的東西，因為GIL不會影響到我想要展示的東西2016-11-11
Python中關(guān)于Sequence切片的下標(biāo)問題詳解
這篇文章主要給大家介紹了Python中關(guān)于Sequence切片下標(biāo)問題的相關(guān)資料，文中通過示例代碼介紹的非常詳細(xì)，對大家具有一定的參考學(xué)習(xí)價值，需要的朋友們下面來一起看看吧。2017-06-06
函數(shù)通常來說就是帶名字的代碼塊,用于完成具體的工作,需要使用的時候調(diào)用即可,這不僅提高代碼的復(fù)用性,而且條理更清晰,函數(shù)定義使用def關(guān)鍵字創(chuàng)建函數(shù),下面通過本文給大家講解python函數(shù)的定義和調(diào)用,感興趣的朋友一起看看吧2024-06-06
本文詳細(xì)介紹了如何使用Anaconda包管理工具創(chuàng)建虛擬環(huán)境,并安裝CUDA加速平臺和PyTorch庫,同時在PyCharm中配置和使用PyTorch進(jìn)行深度學(xué)習(xí)任務(wù),需要的朋友可以參考下2025-02-02
Pandas DataFrame 取一行數(shù)據(jù)會得到Series的方法
今天小編就為大家分享一篇Pandas DataFrame 取一行數(shù)據(jù)會得到Series的方法，具有很好的參考價值，希望對大家有所幫助。一起跟隨小編過來看看吧2018-11-11
這篇文章主要為大家詳細(xì)介紹了PyQt5每天必學(xué)之拖放事件的相關(guān)資料，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價值，感興趣的小伙伴們可以參考一下2018-04-04