这里仍然存在歧义，我不想花时间争论它们。但我想我还是可以添加一些有用的东西;-)
我写的是Python的difflib.SequenceMatcher，并花费了lot寻找预期情况的快速方法来找到最长公共子串的时间。理论上，这应该通过“后缀树”或用“最长公共前缀数组”增强的相关“后缀数组”来完成（如果您想通过 Google 搜索更多信息，引号中的短语是搜索词）。这些可以在最坏情况的线性时间内解决问题。但是，有时会出现这种情况，最坏情况的线性时间算法极其复杂和微妙，并且会受到很大的常数因素的影响 - 如果要搜索给定的语料库，它们仍然可以获得巨大的回报many次，但这不是 Python 的典型情况difflib而且看起来也不像你的情况。
无论如何，我在这里的贡献是重写SequenceMatcher's find_longest_match()返回方法all沿途找到的（局部）最大值匹配。笔记：
我将使用to_words()Raymond Hettinger 为您提供了函数，但没有转换为小写。转换为小写会导致输出与您所说的不完全一样。
然而，正如我在评论中已经指出的那样，这确实输出“quill”，它不在您所需的输出列表中。我不知道为什么不是，因为“羽毛笔”确实出现在两个输入中。
这是代码：
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
Then:
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 and b，画一个矩阵M with len(a)行和len(b)列。在这个应用程序中，我们想要M[i, j]包含以结尾的最长公共连续子序列的长度a[i] and b[j]，计算规则为very easy:
-
M[i, j] = 0 if a[i] != b[j].
-
M[i, j] = M[i-1, j-1] + 1 if a[i] == b[j]（我们假设越界矩阵引用默默地返回 0）。
在这种情况下解释也很容易：存在局部最大值非空比赛结束于a[i] and b[j]，长度M[i, j]，当且仅当M[i, j]是非零但是M[i+1, j+1]为 0 或越界。
您可以使用这些规则编写非常简单且紧凑的代码，其中包含两个循环，用于计算M正确地解决这个问题。缺点是代码将采取（最佳、平均和最坏情况）O(len(a) * len(b)) time and space.
虽然一开始可能会令人困惑，但我发布的代码正是执行上述操作。连接是模糊的，因为代码在多种方面针对预期情况进行了深度优化：
而不是进行一次计算M，然后另一遍解释结果，计算和解释在一次传递中交错a.
因此，不需要存储整个矩阵。相反，只有当前行（newj2len) 和上一行 (j2len）同时存在。
因为这个问题的矩阵是usually大多数为零，这里的行通过将列索引映射到非零值的字典来稀疏地表示。零条目是“免费的”，因为它们永远不会显式存储。
处理一行时，无需迭代每一列：预先计算的b2jdict 准确地告诉我们当前行中有趣的列索引（那些与当前行匹配的列）word from 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
