这篇文章主要介绍了Python实现针对给定字符串寻找最长非重复子串的方法,涉及Python针对字符串的遍历、排序、计算等相关操作技巧,需要的朋友可以参考下
本文实例讲述了Python实现针对给定字符串寻找最长非重复子串的方法。分享给大家供大家参考，具体如下：
问题：
给定一个字符串，寻找其中最长的重复子序列，
本文来源gao!daima.com搞$代!码网
如果字符串是单个字符组成的话如“aaaaaaaaaaaaa”那么满足要求的输出就是a
思路：
这里的思路有两种是我能想到的
（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 "<a href="http://www.gaodaima.com">搞代码</a>测试结果：" 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实现针对给定字符串寻找最长非重复子串的详细内容，更多请关注搞代码gaodaima其它相关文章！
搞代码网（gaodaima.com）提供的所有资源部分来自互联网，如果有侵犯您的版权或其他权益，请说明详细缘由并提供版权或权益证明然后发送到邮箱[email protected]，我们会在看到邮件的第一时间内为您处理，或直接联系QQ：872152909。本网站采用BY-NC-SA协议进行授权
转载请注明原文链接：Python实现针对给定字符串寻找最长非重复子串
转载请注明原文链接：Python实现针对给定字符串寻找最长非重复子串
