查找两个字符串共享的所有n字长的子字符串的最大长度

查找两个字符串共享的所有n字长的子字符串的最大长度

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

我写了Python的

difflib.SequenceMatcher

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

difflib

，它也不像您的案例。

无论如何，我在这里的贡献是重写

SequenceMatcher

的

find_longest_match()

方法，以返回沿途找到的 所有
（本地）最大匹配项。笔记：

1. 我将使用

   to_words()

   Raymond Hettinger提供的功能，但不转换为小写字母。转换为小写字母会导致输出与您想要的输出不完全相同。

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

这是代码：

import redef 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

   if

   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稀疏地表示此处的行。零条目是“免费的”，因为它们从未显式存储。

• 处理一行时，无需遍历每列：预先计算的

  b2j

  dict会准确地告诉我们当前行中有趣的列索引（那些匹配

  word

  from中的当前列

  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