试图找到最长的一致子串

Question

正在尝试查找最长的一致子字符串

假设我有abbbccda，那么我们必须得到“bbb”的索引位置，即[1，3]，因此它应该返回[1，3]。因为统一子字符串从索引1开始，长度为3个字符

其他例子：

“10000111”=>；[1,4]

“aabbbcdaa”=>；[2,5]

解决这个问题的python代码是什么

我的代码很长，很短。忽略打印有这么多可以看到输出

x="aaaabbbbCdAA"
LIST1=[]
for char in x:
    if(char not in LIST1 ):
        LIST1.append(char)

print(LIST1)
list1=[]

for i in LIST1:
    list1.append(x.count(i))

print(list1)

Max_length_Charcater= max(list1)
print(Max_length_Charcater)

index_Max_length_Charcater=list1.index(Max_length_Charcater)
print(index_Max_length_Charcater)

y=LIST1[index_Max_length_Charcater]
print(y)

l=index_Max_length_Charcater
start_of_max_length_character=x.find(y)

for i in range(len(x)):
    if(x[i]==y):
        l+=1
print(l)

print("({0},{1})" .format(start_of_max_length_character,l))

Answer 1

下面是一个正则表达式解决方案：

import re 

strs=("10000111", "aabbbbbCdAA", "abbbccda")

for s in strs:
    uniq=set(s)
    mss=max([max(re.findall(f'{c}+', s), key=len) for c in uniq], key=len)
    print(f'{s}: {s.index(mss)}, {len(mss)}')

印刷品：

10000111: 1, 4
aabbbbbCdAA: 2, 5
abbbccda: 1, 3

您还可以使用groupby执行以下操作：

from itertools import groupby 

for s in strs:
    mss=max([''.join(v) for k,v in groupby(s)], key=len)
    print(f'{s}: {s.index(mss)}, {len(mss)}')
# same output

Answer 2

您可以使用带有zip的列表理解来将字符与其前导字符进行匹配，并识别连续条纹中断的位置。然后，从该位置列表中再次使用zip获取位置范围（从一个断点到下一个断点），可以将其转换为（开始，长度）元组列表。长度最大的元组就是您想要的元组

string = "aabbbbbCdAA"

breaks = [i for i,(a,b) in enumerate(zip(string,string[1:]),1) if a!=b]
ranges = [ (s,e-s) for s,e in zip([0]+breaks,breaks+[len(string)]) ]
print(max(ranges,key=lambda r:r[1]))

breaks列表将包含[2,7,8,9]，它们是字母组的起始位置（暗示位置为零）

ranges列表将通过组合每个组的开头和下一个组的开头（同样使用zip）来形成。这允许计算每组重复的大小：[（0,2）、（2,5）、（7,1）、（8,1）、（9,2）]

如果您觉得有勇气并且想深入研究正则表达式，re模块提供了一种直接获取重复字母的子字符串的方法：

import re

string     = "aabbbbbCdAA"

streaks,_  = zip(*re.findall(r"((.)\2*)",string))
longest    = max(streaks,key=len)

print(string.index(longest),len(longest))
# 2 5