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