这里仍然有歧义，我不想花时间争论它们。但是我想我仍然可以添加一些有用的东西;-)

我写了Python的difflib.SequenceMatcher，并花了 很多
时间来寻找预期情况下快速的方法来找到最长的公共子字符串。从理论上讲，应该使用“后缀树”或相关的“后缀数组”（以“最长公共前缀数组”增强）来完成（如果您想向Google寻求更多信息，引号中的短语为搜索字词）。这些可以解决最坏情况下的线性时间问题。但是，正如有时的情况下，最坏情况下的线性时间的算法是极度复杂和微妙，并受到大的恒定因素-
他们仍然可以还清巨大的，如果给定的语料库将是搜索 很多 次，但是这不是Python的典型案例difflib，它也不像您的案例。

无论如何，我在这里的贡献是重写SequenceMatcher的find_longest_match()方法，以返回沿途找到的 所有
（本地）最大匹配项。笔记：

1. 我将使用to_words()Raymond Hettinger提供的功能，但不转换为小写字母。转换为小写字母会导致输出与您想要的输出不完全相同。

2. 但是，正如我已经在评论中指出的那样，这确实会输出“羽毛笔”，这不在您期望的输出列表中。我不知道为什么不是这样，因为“羽毛笔”确实出现在两个输入中。

这是代码：

import re
def to_words(text):
    'Break text into a list of words without punctuation'
    return re.findall(r"[a-zA-Z']+", text)

def match(a, b):
    # Make b the longer list.
    if len(a) > len(b):
        a, b = b, a
    # Map each word of b to a list of indices it occupies.
    b2j = {}
    for j, word in enumerate(b):
        b2j.setdefault(word, []).append(j)
    j2len = {}
    nothing = []
    unique = set() # set of all results
    def local_max_at_j(j):
        # maximum match ends with b[j], with length j2len[j]
        length = j2len[j]
        unique.add(" ".join(b[j-length+1: j+1]))
    # during an iteration of the loop, j2len[j] = length of longest
    # match ending with b[j] and the previous word in a
    for word in a:
        # look at all instances of word in b
        j2lenget = j2len.get
        newj2len = {}
        for j in b2j.get(word, nothing):
            newj2len[j] = j2lenget(j-1, 0) + 1
        # which indices have not been extended?  those are
        # (local) maximums
        for j in j2len:
            if j+1 not in newj2len:
                local_max_at_j(j)
        j2len = newj2len
    # and we may also have local maximums ending at the last word
    for j in j2len:
        local_max_at_j(j)
    return unique

然后：

a = "They all are white a sheet of spotless paper " \
    "when they first are born but they are to be " \
    "scrawled upon and blotted by every goose quill"
b = "You are all white, a sheet of lovely, spotless " \
    "paper, when you first are born; but you are to " \
    "be scrawled and blotted by every goose's quill"

print match(to_words(a), to_words(b))

显示：

set(['all',
     'and blotted by every',
     'first are born but',
     'are to be scrawled',
     'are',
     'spotless paper when',
     'white a sheet of',
     'quill'])

编辑-工作原理

最好将许多序列匹配和比对算法理解为在二维矩阵上工作，并具有用于计算矩阵条目并随后解释条目含义的规则。

对于输入序列a和b，图像的矩阵M与len(a)行和len(b)列。在此应用程序中，我们要M[i, j]包含以a[i]和结尾的最长公共连续子序列的长度b[j]，并且计算规则 非常 简单：

1. M[i, j] = 0如果a[i] != b[j]。
2. M[i, j] = M[i-1, j-1] + 1如果a[i] == b[j]（假设边界矩阵引用无提示地返回0）。

解读也很容易在这种情况下：有一个当地最大 的非空 在结束比赛a[i]和b[j]，长的M[i, j]，当且仅当M[i, j]是非零但M[i+1, j+1]为0或出界外。

您可以使用这些规则编写带有两个循环的非常简单且紧凑的代码，以M正确计算此问题。缺点是代码将花费（最佳，平均和最差情况）O(len(a) * len(b))时间 和 空间。

虽然一开始可能令人困惑，但我发布的代码完全符合上述要求。连接被遮盖了，因为针对预期情况，代码以多种方式进行了大幅优化：

• 而不是进行一次遍历来计算M，而是进行另一遍来解释结果，计算和解释在一次遍历中交织在一起a。

• 因此，不需要存储整个矩阵。而是仅同时显示当前行（newj2len）和上一行（j2len）。

• 并且由于此问题中的矩阵 通常通常 为零，因此通过将列索引映射到非零值的dict稀疏地表示此处的行。零条目是“免费的”，因为它们从未显式存储。

• 处理一行时，无需遍历每列：预先计算的b2jdict可以准确地告诉我们当前行中有趣的列索引（那些与wordfrom 中的当前列匹配的列a）。

• 最后，部分是偶然的，所有先前的优化都以一种这样的方式进行合谋，即无需知道当前行的索引，因此我们也不必费心计算。

编辑-简单的污垢版本

这是直接实现2D矩阵的代码，没有进行任何优化尝试（否则a Counter通常可以避免显式存储0项）。这非常简单，简短又容易：

def match(a, b):
    from collections import Counter
    M = Counter()
    for i in range(len(a)):
        for j in range(len(b)):
            if a[i] == b[j]:
                M[i, j] = M[i-1, j-1] + 1
    unique = set()
    for i in range(len(a)):
        for j in range(len(b)):
            if M[i, j] and not M[i+1, j+1]:
                length = M[i, j]
                unique.add(" ".join(a[i+1-length: i+1]))
    return unique

当然，;-)返回的结果与match()我最初发布的优化结果相同。

编辑-另一个没有字典

只是为了好玩：-)如果您对矩阵模型有所了解，那么此代码将很容易理解。关于此特定问题的一个值得注意的事情是，矩阵像元的值仅取决于与像元西北方向对角线的值。因此，它足以“穿越”所有主要的对角线，从西边界和北边界的所有像元向东南延伸。这样，无论输入的长度如何，都只需要很小的恒定空间：

def match(a, b):
    from itertools import chain
    m, n = len(a), len(b)
    unique = set()
    for i, j in chain(((i, 0) for i in xrange(m)),
                      ((0, j) for j in xrange(1, n))):
        k = 0
        while i < m and j < n:
            if a[i] == b[j]:
                k += 1
            elif k:
                unique.add(" ".join(a[i-k: i]))
                k = 0
            i += 1
            j += 1
        if k:
            unique.add(" ".join(a[i-k: i]))
    return unique