Python實作針對給定字串尋找最長非重複子字串

這篇文章主要介紹了Python實作針對給定字串尋找最長非重複子字串的方法,涉及Python針對字串的遍歷、排序、計算等相關操作技巧,需要的朋友可以參考下

本文實例講述了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實作在IDLE中輸入多行的方法

以上是Python實作針對給定字串尋找最長非重複子字串的詳細內容。更多資訊請關注PHP中文網其他相關文章！