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