扣丁学堂简述Python实现针对给定字符串寻找最长非重复子串的方法

2018-07-02 13:56:31 467浏览

今天扣丁学堂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实现针对给定字符串寻找最长非重复子串的方法，希望对小伙伴们有所帮助，想要了解更多内容的小伙伴可以登录扣丁学堂官网咨询。扣丁学堂是专业Python培训机构，不仅有专业的老师和与时俱进的课程体系，还有大量的Python视频教程供学员观看学习哦。扣丁学堂Python技术交流群：279521237。

扣丁学堂微信公众号

【关注微信公众号获取更多学习资料】

查看更多关于"Python开发资讯"的相关文章>

标签: Python实现针对给定字符串寻找最长非重复子串的方法 Python培训 Python视频教程 Python基础教程 python安装教程 Python核心编程 Python在线教程 Python在线视频 Python在线学习

上一篇浅谈Python开发之列表插入与替换修改方法下一篇扣丁学堂Pyhon开发中time, strftime和strptime详解

扣丁学堂简述Python实现针对给定字符串寻找最长非重复子串的方法

热门专区

课程推荐