一个重复字符串是由两个相同的字符串首尾拼接而成,例如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:对比字符串,通过索引在原字符串上截取获得的;