这篇文章主要介绍了python实现针对给定字符串寻找最长非重复子串的方法,涉及python针对字符串的遍历、排序、计算等相关操作技巧,需要的朋友可以参考下
本文实例讲述了Python实现针对给定字符串寻找最长非重复子串的方法。分享给大家供大家参考，具体如下：
问题：
给定一个字符串，寻找其中最长的重复子序列，如果字符串是单个字符组成的话如“aaaaaaaaaaaaa”那么满足要求的输出就是a
思路：
立即学习“Python免费学习笔记（深入）”；
这里的思路有两种是我能想到的
（1）从头开始遍历字符串，设置标志位，在往后走的过程中当发现和之前标志位重合的时候就回头检查一下这个新出现的子串是否跟前面字符串或者前面字符串的子串相同，相同则记录该子串并计数加1，直至处理完毕
（2）利用滑窗切片的机制，生成所有的切片接下来统计和处理，主要利用到了两次排序的功能
本文采用的是第二种方法，下面是具体实现：
#!usr/bin/env python#encoding:utf-8'''''__Author__:沂水寒城功能：给定一个字符串，寻找最长重复子串'''from collections import Counterdef 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_listdef 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实现针对给定字符串寻找最长非重复子串的详细内容，更多请关注【创想鸟】其它相关文章！
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容， 请发送邮件至253000106@qq.com举报，一经查实，本站将立刻删除。
发布者：PHP中文网，转转请注明出处：https://www.chuangxiangniao.com/p/2263573.html
