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

百变鹏仔 4小时前 #Python

文章标签字符串

这篇文章主要介绍了python实现针对给定字符串寻找最长非重复子串的方法,涉及python针对字符串的遍历、排序、计算等相关操作技巧,需要的朋友可以参考下

本文实例讲述了Python实现针对给定字符串寻找最长非重复子串的方法。分享给大家供大家参考，具体如下：

问题：

给定一个字符串，寻找其中最长的重复子序列，如果字符串是单个字符组成的话如“aaaaaaaaaaaaa”那么满足要求的输出就是a

思路：

立即学习“Python免费学习笔记（深入）”；

这里的思路有两种是我能想到的

（1）从头开始遍历字符串，设置标志位，在往后走的过程中当发现和之前标志位重合的时候就回头检查一下这个新出现的子串是否跟前面字符串或者前面字符串的子串相同，相同则记录该子串并计数加1，直至处理完毕

（2）利用滑窗切片的机制，生成所有的切片接下来统计和处理，主要利用到了两次排序的功能

本文采用的是第二种方法，下面是具体实现：

#!usr/bin/env python#encoding:utf-8'''''__Author__:沂水寒城功能：给定一个字符串，寻找最长重复子串'''from collections import Counterdef 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_listdef 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]&gt;=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读写Excel文档

自动化环境搭建（Python-selenium）

Python实现二维数组输出为图片_python