Python实现针对给定字符串寻找最长非重复子串的方法
作者：Together_CZ 发布时间：2022-12-05 14:38:53
标签：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程序设计有所帮助。
来源：https://blog.csdn.net/together_cz/article/details/76691723
0
投稿猜你喜欢
- 思路：利用time函数返回的时间字符串与指定时间字符串做比较，相等的时候执行对应的操作。不知道大家的思路是什么，感觉这样比较耗CPU。。。。
python socket多线程实现客户端与服务器连接，供大家参考，具体内容如下之前因为一些作业需要完成一个服务器监听多个客户端的程序，于是- 这篇文章主要介绍了用python写测试数据文件过程解析,文中通过示例代码介绍的非常详细，对大家的学习或者工作具有一定的参考学习价值,需要的朋
- 这篇文章主要介绍了python调用接口的4种方式代码实例,文中通过示例代码介绍的非常详细，对大家的学习或者工作具有一定的参考学习价值,需要的
- 前言其实就是Django RESTful Framework，RESTful一种API的命名风格,主要因为前后端分离开发出现，前后端分离:
- 今天我升级MYSQL到5.1的时候遇到的。写出来共享以下。1、[root@localhost mysql]# scripts/mysql_i
- 今天我将教大家如何用哈希函数将密码加密加密后的密码是很难倒推的~普通加密：首先调用函数hashlibimport hashlib然后使用哈希
- 前言可选链操作符(?.)允许读取位于链接对象链身处的属性的值,而不必明确验证链中的每个引用是否有效。不同之处在于，在引用为空（null或者u
- 时下，个性ico图标却成为一些主流大牌网站提高用户体验（UE）的一个“时髦”玩法，那么，是如何在IE地址栏显示出网站的个性图标的呢？常浏览网
- 学习前言在SSD的框架中，除去tfrecord处理是非常重要的一环之外，slim框架的使用也是非常重要的一环，于是我开始学习slim啦sli
- 重复的数据可能有这样两种情况，第一种: 表中只有某些字段一样，第二种是两行记录完全一样。一、对于部分字段重复数据的删除 1.查询重复的数据
- 限制访问可以基于某种权限，某些检查或者为login视图提供不同的位置，这些实现方式大致相同。一般的方法是直接在视图的 request.use
- 本文实例讲述了Python类的用法。分享给大家供大家参考。具体如下：先看一段代码：#!/usr/bin/env pythonclass Te
- 数据库系统的安全性包括很多方面。由于很多情况下，数据库服务器容许客户机从网络上连接，因此客户机连接的安全对MySQL数据库安全有很重要的影响
- 本文实例讲述了kNN算法python实现和简单数字识别的方法。分享给大家供大家参考。具体如下：kNN算法算法优缺点：优点：精度高、对异常值不
- 随着PHP4.0和JSP技术的推出以及IIS中不断出现的重大的安全问题，MicroSoft的ASP的市场仿佛是变的狭窄了，但是 MicroS
- 今天呱呱发了一个网址给我看，大概效果就是类似幻灯片的效果。当时我的第一反映这个是不是用锚点做的啊呢，以前在网上看过用锚点做的这类的效果。脑袋
- 中文简繁体网页的转换FrontPage 2002提供了中文简繁体转换的功能。只要轻轻一点就可做出简体或繁体中文网站了。如要将当前
- 一、Pythont如何打开 txt 格式的文件？1.首先我使用pycharm创建一个项目，然后在这个项目里面再创建一个python的包，然后
- Rs.Open参数说明在ASP中经常用Rs.Open sql,conn,1,1这样的方式打开数据库,但仍有一部分同行不知道这是嘛意思,现整理
