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

yipeiwu_com7年前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程序设计有所帮助。

相关文章

pandas基于时间序列的固定时间间隔求均值的方法

pandas基于时间序列的固定时间间隔求均值的方法

如果index是时间序列就不用转datetime;但是如果时间序列是表中的某一列,可以把这一列设为index 例如: 代码: DF=df2.set_index(df1['time_...

python实现通过flask和前端进行数据收发

python代码: # -*- coding: utf-8 -*- from flask import Flask,jsonify,render_template,request i...

使用django的objects.filter()方法匹配多个关键字的方法

介绍: 今天在使用django的时候忽然想用到,如何匹配多个关键字的操作,我们知道django有一个objects.filter()方法,我们可以通过如下一句代码实现匹配数据库中titl...

pyshp创建shp点文件的方法

如下所示: # coding:utf-8 import shapefile w = shapefile.Writer() w.autoBalance = 1 w = shapef...

Python enumerate函数功能与用法示例

本文实例讲述了Python enumerate函数功能与用法。分享给大家供大家参考,具体如下: eunmerate在英文中是列举、枚举的意思,在python中eunmerate()是一个...