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字符串操作技巧汇总》、《Python数据结构与算法教程》、《Python函数使用技巧总结》、《Python入门与进阶经典教程》及《Python文件与目录操作技巧汇总》

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

您可能感兴趣的文章:

  • Python回文字符串及回文数字判定功能示例
  • python根据给定文件返回文件名和扩展名的方法
  • Python计算回文数的方法
  • python实现求最长回文子串长度
  • Python实现读取字符串按列分配后按行输出示例
  • Python 字符串操作方法大全
  • python判断字符串是否包含子字符串的方法
  • python字符串连接的N种方式总结
  • python分割和拼接字符串
  • python统计字符串中指定字符出现次数的方法
  • Python针对给定字符串求解所有子序列是否为回文序列的方法
赞 (0)

相关推荐

  • Python 字符串操作方法大全

    1.去空格及特殊符号 复制代码 代码如下: s.strip().lstrip().rstrip(',') 2.复制字符串 复制代码 代码如下: #strcpy(sStr1,sStr2)sStr1 = 'strcpy'sStr2 = sStr1sStr1 = 'strcpy2'print sStr2 3.连接字符串 复制代码 代码如下: #strcat(sStr1,sStr2)sStr1 = 'strcat'sStr2 = 'append'sStr1 += sStr2print sStr1 4.查

  • Python实现读取字符串按列分配后按行输出示例

    本文实例讲述了Python实现读取字符串按列分配后按行输出.分享给大家供大家参考,具体如下: 问题: 输入一个字符串和一个数字,数字代表分为几行,需要按照给定的列存储方法存储下来之后按行拼接读出,如: 输入:TNGDWXAZQSCVBK,3 输出:TWQBNDXZSVKGAC 中间转化的时候会形成这样的图形: T   W   Q   K N D X Z S V B G   A   C 化为矩阵可能看得更清晰一点: T 0 W 0 Q 0 B N D X Z S V K G 0 A 0 C 0 0

  • Python针对给定字符串求解所有子序列是否为回文序列的方法

    Python针对给定字符串求解所有子序列是否为回文序列的方法

    本文实例讲述了Python针对给定字符串求解所有子序列是否为回文序列的方法.分享给大家供大家参考,具体如下: 问题: 给定一个字符串,得到所有的子序列,判断是否为回文序列 思路: 对字符串遍历切片即可 下面是具体实现: #!usr/bin/env python # -*- coding:utf-8 -*- ''''' __AUthor__:沂水寒城 功能:对指定字符串寻找所有回文子序列 ''' def is_huiwen(one_str_list): ''''' 输入一个字符串列表,判断是否为回

  • python根据给定文件返回文件名和扩展名的方法

    本文实例讲述了python根据给定文件返回文件名和扩展名的方法.分享给大家供大家参考.具体分析如下: 这段代码可以根据文件的完整路径返回文件名和扩展名,python的函数可以同时返回两个值,用起来就更方便了 def GetFileNameAndExt(filename): import os (filepath,tempfilename) = os.path.split(filename); (shotname,extension) = os.path.splitext(tempfilename

  • python实现求最长回文子串长度

    给定一个字符串,求它最长的回文子串长度,例如输入字符串'35534321',它的最长回文子串是'3553',所以返回4. 最容易想到的办法是枚举出所有的子串,然后一一判断是否为回文串,返回最长的回文子串长度.不用我说,枚举实现的耗时是我们无法忍受的.那么有没有高效查找回文子串的方法呢?答案当然是肯定的,那就是中心扩展法,选择一个元素作为中心,然后向外发散的寻找以该元素为圆心的最大回文子串.但是又出现了新的问题,回文子串的长度即可能是基数,也可能好是偶数,对于长度为偶数的回文子串来说是不存在中心元

  • python统计字符串中指定字符出现次数的方法

    本文实例讲述了python统计字符串中指定字符出现次数的方法.分享给大家供大家参考.具体如下: python统计字符串中指定字符出现的次数,例如想统计字符串中空格的数量 s = "Count, the number of spaces." print s.count(" ") x = "I like to program in Python" print x.count("i") PS:本站还提供了一个关于字符统计的工具,感兴

  • python字符串连接的N种方式总结

    python中有很多字符串连接方式,今天在写代码,顺便总结一下: 最原始的字符串连接方式:str1 + str2 python 新字符串连接语法:str1, str2 奇怪的字符串方式:str1 str2 % 连接字符串:'name:%s; sex: ' % ('tom', 'male') 字符串列表连接:str.join(some_list) 第一种,想必只要是有编程经验的人,估计都知道,直接用 "+" 来连接两个字符串: 'Jim' + 'Green' = 'JimGreen' 第

  • python判断字符串是否包含子字符串的方法

    本文实例讲述了python判断字符串是否包含子字符串的方法.分享给大家供大家参考.具体如下: python的string对象没有contains方法,不用使用string.contains的方法判断是否包含子字符串,但是python有更简单的方法来替换contains函数. 方法1:使用 in 方法实现contains的功能: site = 'http://www.jb51.net/' if "jb51" in site: print('site contains jb51') 输出结

  • Python计算回文数的方法

    本文实例讲述了Python计算回文数的方法.分享给大家供大家参考.具体如下: 这里检查数字是不是回文数,用196算法生成一个数字的回文数 num = 905; def is_Palindrome(num): """ 判断一个数字是不是回文数,这里有些取巧了 :param num: :return: """ """ :param num: :return: """ temp = "

  • python分割和拼接字符串

    关于string的split 和 join 方法对导入os模块进行os.path.splie()/os.path.join() 貌似是处理机制不一样,但是功能上一样. 1.string.split(str=' ',num=string.count(str)): 以str为分隔,符切片string,如果num有指定值,则仅分隔num个子字符串.S.split([sep [,maxsplit]]) -> 由字符串分割成的列表 返回一组使用分隔符(sep)分割字符串形成的列表.如果指定最大分割数,则在

  • Python回文字符串及回文数字判定功能示例

    本文实例讲述了Python回文字符串及回文数字判定功能.分享给大家供大家参考,具体如下: 所谓回文字符串,就是一个字符串,从左到右读和从右到左读是完全一样的.回文数字也是如此. python2代码如下: def huiwen(s): s1=str(s) if s1==''.join(reversed(s1)): return True else: return False 运行结果: >>> huiwen('abccba') True >>> huiwen('abc')

随机推荐