Python實(shí)現(xiàn)針對(duì)給定字符串尋找最長(zhǎng)非重復(fù)子串的方法
本文實(shí)例講述了Python實(shí)現(xiàn)針對(duì)給定字符串尋找最長(zhǎng)非重復(fù)子串的方法。分享給大家供大家參考，具體如下：
問(wèn)題：
給定一個(gè)字符串，尋找其中最長(zhǎng)的重復(fù)子序列，如果字符串是單個(gè)字符組成的話如“aaaaaaaaaaaaa”那么滿足要求的輸出就是a
思路：
這里的思路有兩種是我能想到的
（1）從頭開(kāi)始遍歷字符串，設(shè)置標(biāo)志位，在往后走的過(guò)程中當(dāng)發(fā)現(xiàn)和之前標(biāo)志位重合的時(shí)候就回頭檢查一下這個(gè)新出現(xiàn)的子串是否跟前面字符串或者前面字符串的子串相同，相同則記錄該子串并計(jì)數(shù)加1，直至處理完畢
（2）利用滑窗切片的機(jī)制，生成所有的切片接下來(lái)統(tǒng)計(jì)和處理，主要利用到了兩次排序的功能
本文采用的是第二種方法，下面是具體實(shí)現(xiàn)：
#!usr/bin/env python
#encoding:utf-8
'''''
__Author__:沂水寒城
功能：給定一個(gè)字符串，尋找最長(zhǎng)重復(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 "腳本之家測(cè)試結(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)容可查看本站專(zhuān)題：《Python字符串操作技巧匯總》、《Python數(shù)據(jù)結(jié)構(gòu)與算法教程》、《Python函數(shù)使用技巧總結(jié)》、《Python入門(mén)與進(jìn)階經(jīng)典教程》及《Python文件與目錄操作技巧匯總》
希望本文所述對(duì)大家Python程序設(shè)計(jì)有所幫助。
相關(guān)文章
這篇文章主要為大家詳細(xì)介紹了python爬取淘寶商品的銷(xiāo)量信息，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2018-11-11
python模型集成知識(shí)點(diǎn)總結(jié)
在本篇文章里小編給大家整理了一篇關(guān)于python模型集成知識(shí)點(diǎn)總結(jié)，有需要的朋友們可以學(xué)習(xí)參考下。2021-08-08
python使用mysqldb連接數(shù)據(jù)庫(kù)操作方法示例詳解
這篇文章主要介紹了python mysqldb使用方法,大家參考使用2013-12-12
在Python中實(shí)現(xiàn)單例模式,意味著一個(gè)類(lèi)只能創(chuàng)建一個(gè)實(shí)例,單例模式在某些場(chǎng)景下非常有用,比如當(dāng)你需要控制資源的訪問(wèn),或者當(dāng)你想確保全局只有一個(gè)對(duì)象實(shí)例時(shí),本文給大家介紹了幾種在Python中實(shí)現(xiàn)單例模式的方法,需要的朋友可以參考下2024-03-03
Pytorch訓(xùn)練模型得到輸出后計(jì)算F1-Score 和AUC的操作
這篇文章主要介紹了Pytorch訓(xùn)練模型得到輸出后計(jì)算F1-Score 和AUC的操作，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。如有錯(cuò)誤或未考慮完全的地方，望不吝賜教2021-05-05
Python正則表達(dá)式中flags參數(shù)的實(shí)例詳解
正則表達(dá)式是一個(gè)很強(qiáng)大的字符串處理工具,幾乎任何關(guān)于字符串的操作都可以使用正則表達(dá)式來(lái)完成,下面這篇文章主要給大家介紹了關(guān)于Python正則表達(dá)式中flags參數(shù)的相關(guān)資料,需要的朋友可以參考下2022-04-04
python保留格式匯總各部門(mén)excel內(nèi)容的實(shí)現(xiàn)思路
這篇文章主要介紹了python保留格式匯總各部門(mén)excel內(nèi)容,本文通過(guò)實(shí)例代碼給大家介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值，需要的朋友可以參考下2020-06-06![詳解pandas中利用DataFrame對(duì)象的.loc[]、.iloc[]方法抽取數(shù)據(jù)](http://img.jbzj.com/images/xgimg/bcimg7.png)
詳解pandas中利用DataFrame對(duì)象的.loc[]、.iloc[]方法抽取數(shù)據(jù)
這篇文章主要介紹了pandas中利用DataFrame對(duì)象的.loc[]、.iloc[]方法抽取數(shù)據(jù)，文中通過(guò)示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧2020-12-12
Python基于輾轉(zhuǎn)相除法求解最大公約數(shù)的方法示例
這篇文章主要介紹了Python基于輾轉(zhuǎn)相除法求解最大公約數(shù)的方法,結(jié)合實(shí)例形式分析了Python使用輾轉(zhuǎn)相除法求解最大公約數(shù)的實(shí)現(xiàn)方法與優(yōu)化操作技巧,需要的朋友可以參考下2018-04-04
Python實(shí)現(xiàn)簡(jiǎn)單猜數(shù)字游戲
這篇文章主要為大家詳細(xì)介紹了Python實(shí)現(xiàn)猜數(shù)字游戲，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2021-02-02