用python实现,找出一个字符串中的重复字符子串和字符串数量

发布网友 发布时间：2022-04-23 16:38

我来回答

共3个回答

懂视网 时间：2022-05-10 10:58

本文实例讲述了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)

结果如下：

热心网友 时间：2022-05-10 08:06

代码如下:

【备注】:

1. 用str.split(',')只能分隔逗号一种；如果涉及到多重分隔的话就需要使用re.split(',|:')。

2. 原字符串以逗号分隔的，后面有一个或多个字符串，所以re.split(', | ')。

3. 执行re.split(r', | ', S)操作之后，列表中会产生大量的''，就需要将filter过滤掉。

4. 使用L.count(x) == 1 或者 L.count(x) > 1来保留重复项或，非重复项。

5. set(L)则是保留列表中的唯一项，再用list()将其转换为列表。

6. 使用', '.join(L)，将列表拼接成我们想要的字符串。

热心网友 时间：2022-05-10 09:24