Python找出字符串中的最长重复子串

2021/8/5 14:36:09

本文主要是介绍Python找出字符串中的最长重复子串,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

一个重复字符串是由两个相同的字符串首尾拼接而成,例如abcabc便是长度为6的一个重复字符串,而abcba则不存在重复字符串。 给定任意字符串,请帮小强找出其中的最长重复子串。

str1 = 'abcdiiabcdiierwyqu'
# 设默认的最长重复字符串长度
print('str1:', str1, '长度为:', len(str1))
str1_start = 0
result = 0
for str1_max in reversed(range(0, int(len(str1) / 2))):
    for i in range(0, int(len(str1) / 2 - 1)):
        temp = str1[str1_start + i:str1_max + i]
        if str1.count(temp, str1_start + i, (str1_max + i)*2) == 2:
            result = str1_max
            break
    if result != 0:
        print('重复字符串的最大长度为:', str1_max)
        break

思路:例如字符串str=abcabciif,重复字符串的长度一定不会超过整个字符串长度的一半。注:abcabciif重复字符串的长度为:3
我们只用一个count()函数就可解决这个问题,我们首先假设有一半的字符都重复即len(str)/2,然后我们检测整个字符串中含有前一半字符串的个数,str.count(对比字符串, 对比字符串开始的索引, 对比字符串结束的索引的两倍),只要这个能返回2,就证明对比字符串长度为最长的。具体循环可看代码
result:表示最长重复字符串的长度,即结果
str1_start:对比字符串截取的开始索引;
str1_max:对比字符串的长度,开始时为原字符串的一半;
temp:对比字符串,通过索引在原字符串上截取获得的;



这篇关于Python找出字符串中的最长重复子串的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!


扫一扫关注最新编程教程