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

yipeiwu_com5年前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 "【听图阁-专注于Python设计】测试结果:"
  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文件与目录操作技巧汇总

希望本文所述对大家Python程序设计有所帮助。

相关文章

python正则表达式之对号入座篇

python正则表达式之对号入座篇

一、定义 正则表达式是对字符串操作的一种逻辑公式,就是用事先定义好的一些特定字符、及这些特定字符的组合,组成一个“规则字符串”,这个“规则字符串”用来表达对字符串的一种过滤逻辑。如果找到...

python3.6数独问题的解决

python3.6数独问题的解决

算法比较暴力,直接用穷举的方式一个一个去试,所以程序运行时间会比较长,运行时间视数独而定。 不过从一开始到运行成功,整个过程却是一波三折,设计算法就花了不少时间,然后就是不断地去调试,找...

python实现二分类的卡方分箱示例

解决的问题: 1、实现了二分类的卡方分箱; 2、实现了最大分组限定停止条件,和最小阈值限定停止条件; 问题,还不太清楚,后续补充。 1、自由度k,如何来确定,卡方阈值的自由度为 分箱数-...

python sqlite的Row对象操作示例

本文实例讲述了python sqlite的Row对象操作。分享给大家供大家参考,具体如下: 一 代码 import sqlite3 conn=sqlite3.connect("tes...

Python正则表达式匹配和提取IP地址

Linux No.1 IPv4 下面是IPv4的IP正则匹配实例: 简单的匹配给定的字符串是否是ip地址 import re if re.match(r"^(?:[0-9]{...