最长重复子串

Question

我正在学习Python，以完成我的学校作业。基本上，我需要在字符串列表中找到最长的重复子字符串，如此处所示。我已经阅读了这篇文章，并且理解了我应该做什么。

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

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'作为我最长的子字符串，但我还没有想出一种方法来实现这一点。似乎只有在列表的所有项目中匹配子字符串时，我才能匹配子字符串。如何修改我的代码/逻辑以获取出现多次的最长子字符串？

谢谢。

- KidBatman

Answer 1

您只能在所有项中匹配子字符串，因为这正是您所要求的：

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

此函数在至少两个单词中找到最长的子字符串（如果列表为空或只包含空字符串，则会返回None），并给出以下结果：

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

请注意，一旦您删除要求子字符串必须在所有字符串中出现的限制，则您第一个单词列表中最长的单词实际上是“lid”。

- jonrsharpe

---

你能修改一下代码，让它返回在所有输入字符串中可能不存在的最长完整单词序列吗？我在这里发布了一个相关问题：https://stackoverflow.com/questions/62149929/find-longest-sequence-of-common-words-from-list-of-words-in-python - Stelios M

Answer 2

如果你真的想要 blah，那么你需要删除最长公共子序列必须存在于所有字符串中的条件。因此，你可以这样做（注意，第一个示例中你会得到 lid）：

def allCommonSubstrings(s1, s2):
    answer = set()
    if len(s1) > len(s2):
        s1, s2 = s2, s1
    for i in range(len(s1)):
        for j in range(i+1, len(s1)+1):
            if s1[i:j] in s2:
                answer.add(s1[i:j])
    return answer

def longestCommonSubstring(strings):
    common = set()
    for s1,s2 in itertools.combinations(strings, 2):
        common = common.union(allCommonSubstrings(s1, s2))
    return max(common, key=len)

In [288]: longestCommonSubstring(['slide', 'glidb', 'flidt', 'cridz', 'bidr', 'balh', 'tejka', 'djakljskdl', 'blah', 'blah', 'blah'])
Out[288]: 'blah'

In [289]: longestCommonSubstring(['slide', 'glidb', 'flidt', 'cridz', 'bidr'])
Out[289]: 'lid'

- inspectorG4dget