Python实现针对给定字符串寻找最长非重复子串的方法 - CSDN文库

python字符串操作

125 浏览量更新于2023-03-03 收藏 56KB PDF 举报

身份认证购VIP最低享 7 折!

领优惠券(最高得80元）

资源详情

资源推荐

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

+=1

else:

res_dict

=1

sorted_list=sorted(res_dict.items(), key=lambda e:e[1], reverse=True)

tmp_list=

>=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入门与进阶经典教程》及《Python文件与目录操作技巧汇总》

本内容试读结束，登录后可阅读更多

下载后可阅读完整内容，剩余1页未读，立即下载

weixin_38722164

粉丝: 2
资源: 913

会员权益专享

图片转文字

全年可省5，000元立即开通

最新资源

资源上传下载、课程学习等过程中有任何疑问或建议，欢迎提出宝贵意见哦~我们会及时处理！点击此处反馈