在我去学校工作时学习 python。本质上,我需要在字符串列表中找到最长的重复子字符串,如图 here 所示。我一直在阅读 this article 并了解我应该做什么。
到目前为止,我的实现如下:
def long_rptr_subString(testList):
longSubstring = ''
if len(testList) > 1 and len(testList[0]) > 0:
for i in range(len(testList[0])):
for j in range(len(testList[0])-i+1):
if j > len(longSubstring) and all(testList[0][i:i+j] in x for x in testList):
longSubstring = testList[0][i:i+j]
return longSubstring
现在当我用
['slide', 'glidb', 'flidt', 'cridz', 'bidr']
调用我的函数时我得到
'id'
的正确结果是我最长的子字符串。但是,当我通过列表
['slide', 'glidb', 'flidt', 'cridz', 'bidr', 'balh', 'tejka', 'djakljskdl', 'blah', 'blah', 'blah']
时,我没有得到任何返回结果。我应该找回 'blah'
作为我最长的子字符串,但我还没有想出一种方法来实现这一点。似乎我只能在列表的所有项目中匹配子字符串。我如何修改我的代码/逻辑以获得出现不止一次的最长子字符串?谢谢你。
最佳答案
您只能匹配 all
项目中的子字符串,因为这正是您所要求的:
all(testList[0][i:i+j] in x for x in testList)
即使您更改它,您也只能找到第一个子字符串中最长的子字符串,因为您只能通过
testlist[0]
进行检查。相反,请尝试以下操作:
def longest_substr(lst):
longest = None
for word in lst:
for i in range(len(word)):
for j in range(i+1, len(word)+1):
if ((longest is None or (j - i > len(longest))) and
sum(word[i:j] in w for w in lst) > 1):
longest = word[i:j]
return longest
这会找到至少两个 (
> 1
) 单词中的最长子字符串(或者将 return None
用于空列表或空字符串列表),并给出以下结果:>>> longest_substr(['slide', 'glidb', 'flidt', 'cridz', 'bidr'])
'lid'
>>> longest_substr(['slide', 'glidb', 'flidt', 'cridz', 'bidr', 'balh', 'tejka', 'djakljskdl', 'blah', 'blah', 'blah'])
'blah'
请注意,一旦取消了子字符串必须在所有字符串中的要求,第一个单词列表中最长的实际上是
'lid'
。关于python - 最长重复子串,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/21930757/