Python给定字符串寻找最长非重复子串 Python实现针对给定字符串寻找最长非重复子串的方法
Together_CZ 人气:0想了解Python实现针对给定字符串寻找最长非重复子串的方法的相关内容吗，Together_CZ在本文为您仔细讲解Python给定字符串寻找最长非重复子串的相关知识和一些Code实例，欢迎阅读和指正，我们先划重点：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程序设计有所帮助。
加载全部内容