Python实现针对给定字符串寻找最长非重复子串

  • 更新时间:2022-09-23 09:37:09
  • 编辑:文安福
这篇文章主要介绍了Python实现针对给定字符串寻找最长非重复子串的方法,涉及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实现针对给定字符串寻找最长非重复子串

 

以上就是Python实现针对给定字符串寻找最长非重复子串的详细内容,更多请关注码农之家其它相关文章!

相关教程

  • Python3列表内置方法实例讲解

    这篇文章主要介绍了Python3列表内置方法大全及示例代码小结,非常不错,具有一定的参考借鉴价值,需要的朋友可以参考下

    发布时间:2021-06-10

  • Python设计模式之观察者模式简单示例

    这篇文章主要介绍了Python设计模式之观察者模式,简单描述了观察者模式的概念、原理,并结合实例形式分析了Python观察者模式的相关定义与使用技巧,需要的朋友可以参考下

    发布时间:2022-04-25

  • 实例详解Python中 CSV格式清洗与转换

    这篇文章主要介绍了Python123 CSV格式清洗与转换的实例代码,非常不错,具有一定的参考借鉴价值,需要的朋友可以参考下

    发布时间:2020-01-20

  • linux开机自启动python程序代码方法

    在本篇文章中小编给大家分享了关于linux开机自启动python程序代码方法,对此有需要的朋友们学习下。

    发布时间:2019-07-03

  • python多版本下设置python3为默认的方法

    这篇文章主要介绍了如何在双python下设置python3为默认,本文通过一个例子分步骤给大家介绍的非常详细,具有一定的参考借鉴价值,需要的朋友可以参考下

    发布时间:2019-06-06

  • Python字符串处理示例代码

    这篇文章主要介绍了Python字符串处理的8招秘籍,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧

    发布时间:2020-02-17

  • Python画个美国队长队盾牌实例教程

    这篇文章主要介绍了用Python练习画个美队盾牌,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧

    发布时间:2019-06-19

  • Python中@property装饰器的使用技巧性解析(代码示例)

    本篇文章给大家带来的内容是关于Python中@property装饰器的技巧性用法(代码示例),有一定的参考价值,有需要的朋友可以参考一下,希望对你有所帮助。​

    发布时间:2020-01-28

用户留言