溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
本文實例講述了Python實現針對給定字符串尋找最長非重復子串的方法。分享給大家供大家參考，具體如下：
問題：
給定一個字符串，尋找其中最長的重復子序列，如果字符串是單個字符組成的話如“aaaaaaaaaaaaa”那么滿足要求的輸出就是a
思路：
這里的思路有兩種是我能想到的
（1）從頭開始遍歷字符串，設置標志位，在往后走的過程中當發現和之前標志位重合的時候就回頭檢查一下這個新出現的子串是否跟前面字符串或者前面字符串的子串相同，相同則記錄該子串并計數加1，直至處理完畢
（2）利用滑窗切片的機制，生成所有的切片接下來統計和處理，主要利用到了兩次排序的功能
本文采用的是第二種方法，下面是具體實現：
#!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程序設計有所幫助。
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
