Python實(shí)現(xiàn)針對(duì)給定字符串尋找最長(zhǎng)非重復(fù)子串的方法

發(fā)布時(shí)間：2020-10-24 23:01:50 來(lái)源：腳本之家閱讀：186 作者：Together_CZ 欄目：開(kāi)發(fā)技術(shù)

本文實(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é)果如下：

Python實(shí)現(xiàn)針對(duì)給定字符串尋找最長(zhǎng)非重復(fù)子串的方法

更多關(guān)于Python相關(guān)內(nèi)容可查看本站專題：《Python字符串操作技巧匯總》、《Python數(shù)據(jù)結(jié)構(gòu)與算法教程》、《Python函數(shù)使用技巧總結(jié)》、《Python入門與進(jìn)階經(jīng)典教程》及《Python文件與目錄操作技巧匯總》

希望本文所述對(duì)大家Python程序設(shè)計(jì)有所幫助。

向AI問(wèn)一下細(xì)節(jié)

Python實(shí)現(xiàn)針對(duì)給定字符串尋找最長(zhǎng)非重復(fù)子串的方法

猜你喜歡

最新資訊

相關(guān)推薦

相關(guān)標(biāo)簽