给定一个长字符串，找到重复时间最长的子字符串。
当然，暴力方法是找到所有子字符串并检查剩余字符串的子字符串，但有问题的字符串有数百万个字符(如DNA序列、AGGCTAGCT等(，我希望在宇宙崩溃之前完成。
尝试了很多方法，我有一个解决方案，它在高达数百万的字符串上运行得很快，但对于较大的字符串来说，它实际上需要很长时间(6+小时(，尤其是当重复序列的长度变得很长时。
def find_lrs(text, cntr=2):
sol = (0, 0, 0)
del_list = ['01','01','01']
while len(del_list) != 0:
d = defaultdict(list)
for i in range(len(text)):
d[text[i:i + cntr]].append(i)
del_list = [(item, d[item]) for item in d if len(d[item]) > 1]
# if list is empty, we're done
if len(del_list) == 0:
return sol
else:
sol = (del_list[0][1][0], (del_list[0][1][1]),len(del_list[0][0]))
cntr += 1
return sol
我知道这很难看，但嘿，我是个初学者，我很高兴我有工作要做。想法是遍历以长度为2的子字符串为键的字符串，子字符串的索引为值。如果文本是，比如说，"BANANA"，在第一次通过后，dict会看起来像这样：
｛'BA'：[0]，'AN'：[1，3]，'NA'：[2，4]，'A'：[5]｝
BA只显示一次，从索引0开始。AN和NA出现两次，分别出现在索引的1/3和2/4处。
然后我创建了一个列表，其中只包括至少出现两次的键。在上面的例子中，我们可以删除BA，因为它只出现过一次——如果没有以"BA"开头的长度为2的子字符串，那么就不会有以BA开头的长度3的子字符串。因此，经过修剪的列表中的第一个过去是：[(AN'，[1,3](，('NA'，[2,4](]
由于至少有两种可能性，我们保存迄今为止找到的最长的子字符串和索引，并将子字符串长度增加到3。我们继续，直到没有子字符串重复为止。
如前所述，这在大约2分钟内对1000万个字符串有效，这显然是合理的——但是，最长的重复序列相当短。在一个较短但重复时间较长的字符串上，运行需要-小时。我怀疑这与字典有多大有关，但不太清楚为什么。
当然，我想做的是通过删除显然没有重复的子字符串来保持字典的简短，但我不能在迭代字典时从字典中删除项目。我知道有后缀树方法，这些方法-目前-超出了我的能力范围。
可能只是这超出了我目前的知识范围，这当然很好，但我忍不住动摇了有解决方案的想法。
我忘记更新了。在离开我的电脑，在iPad上写下小图表，再次查看了我的代码后，我意识到上面的代码并没有做我认为它在做的事情。
如上所述，我的攻击计划是从遍历以长度为2的子字符串为键的字符串开始，子字符串的索引为值，创建一个列表，只捕获至少发生两次的长度为2个子字符串，并且只查看这些位置。
一切都很好，但仔细看，你会发现我从来没有真正更新默认字典，使其只有两个或更多重复的位置//头撞在桌子上。
我最终想出了两个解决方案。第一个解决方案使用了一种略有不同的方法，即"排序后缀"方法。这会得到单词的所有后缀，然后按字母顺序对它们进行排序。例如；BANANA"；，排序为：A.ANA阿那香蕉NANANA
然后，我们查看每一个相邻的后缀，找出每一对开始有多少个共同的字母。A和ANA只有"A"的共同点。ANA和ANANA具有"；ANA"；一般来说，所以我们有长度3作为最长的重复子串。ANANA和BANANA一开始没有任何共同点，BANANA和NA也是如此；NA"；共同的因此，长度为3的"ANA"是重复时间最长的子字符串。
我做了一个小助手函数来做实际的比较。代码如下：
def longest_prefix(suf1, suf2, mx=None):
min_len = min(len(suf1), len(suf2))
for i in range(min_len):
if suf1[i] != suf2[i]:
return (suf1[0:i], len(suf1[0:i]))
return (suf1[0:i], len(suf1[0:i]))
def longest_repeat(txt):
lst = sorted([text[i:] for i in range(len(text))])
print(lst)
mxLen = 0
mx_string = ""
for x in range(len(lst) - 1):
temp = longest_prefix(lst[x], lst[x + 1])
if temp[1] > mxLen:
mxLen = temp[1]
mx_string = temp[0]
first = txt.find(mx_string)
last = txt.rfind(mx_string)
return (first, last, mxLen)
这是有效的。然后我回去重新查看我的原始代码，发现我没有重置字典。关键是，每次通过后，我都会更新字典，只查看重复的候选者。
def longest_repeat(text):
# create the initial dictionary with all length-2 repeats
cntr = 2 # size of initial substring length we look for
d = defaultdict(list)
for i in range(len(text)):
d[text[i:i + cntr]].append(i)
# find any item in dict that wasn't repeated at least once
del_list = [(d[item]) for item in d if len(d[item]) > 1]
sol = (0,0,0)
# Keep looking as long as del_list isn't empty,
while len(del_list) > 0:
d = defaultdict(list) # reset dictionary
cntr += 1 # increment search length
for item in del_list:
for i in item:
d[text[i:i + cntr]].append(i)
# filter as above
del_list = [(d[item]) for item in d if len(d[item]) > 1]
# if not empty, update solution
if len(del_list) != 0:
sol = (del_list[0][0], del_list[0][1], cntr)
return sol
这是相当快的，我认为它更容易遵循。