最长重复子串

本文介绍了最长重复子串的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

在我去上学的同时学习 Python.本质上，我需要在字符串列表中找到最长的重复子字符串，如此处.我一直在阅读这篇文章，并对我应该做的事情有所了解.

learning python as I go for school work. Essentially, I need to find the longest repeated substring in a list of string as shown here. I have been reading through this article and have an understanding of what I should do.

到目前为止，我的实现如下:

so far my implementation is as follows:

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'的正确结果.

now when I call my function with let's say ['slide', 'glidb', 'flidt', 'cridz', 'bidr'] I get the correct result of 'id' as being my longest substring.

但是，当我通过列表 ['slide'，'glidb'，'flidt'，'cridz'，'bidr'，'balh'，'tejka'，'djakljskdl'，'blah'，'等等'，

However, when I pass the list ['slide', 'glidb', 'flidt', 'cridz', 'bidr', 'balh', 'tejka', 'djakljskdl', 'blah', 'blah', 'blah'] I don't get any return results. I should be getting back 'blah' as my longest substring, but I haven't figured out a way to accomplish this. It seems I am only able to match substrings when they are in ALL items of the list. How might I modify my code/logic to get the longest substring that occurs more than once?

谢谢.

推荐答案

您只能匹配 all 项目中的子字符串，因为这正是您要的:

You can only match substrings in all items because that's exactly what you ask for:

all(testList[0][i:i+j] in x for x in testList)

即使您进行了更改，也只能找到 first 子字符串中最长的子字符串，因为您只能通过 testlist [0] 进行检查.

Even if you change that, you can only find the longest substring that is in the first substring, because you only check through testlist[0] .

相反，请尝试以下操作:

Instead, try something like:

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 )个单词中最长的子字符串(或者对于空列表或空字符串列表，不返回)并给出以下结果:

This finds the longest substring that's in at least two (> 1) of the words (or will return None for an empty list or list of empty strings) and gives me the following results:

>>> longest_substr(['slide', 'glidb', 'flidt', 'cridz', 'bidr']) 'lid' >>> longest_substr(['slide', 'glidb', 'flidt', 'cridz', 'bidr', 'balh', 'tejka', 'djakljskdl', 'blah', 'blah', 'blah']) 'blah'

请注意，一旦删除了必须在所有字符串中包含子字符串的要求，则第一个单词列表中最长的实际上就是'lid'.

Note that, once you remove the requirement that the substring must be in all strings, the longest in your first list of words is actually 'lid'.