<p>在我的书中,这个算法叫做字符串匹配。它在O(<em>mn</em>)中运行,其中<em>m</em>和<em>n</em>是单词长度。我想它也可以运行在完整的单词上,什么是最有效的将取决于预期的常用字母数量以及排序和过滤是如何执行的。我将解释它的普通字母字符串,因为这更容易</p>
<p>其思想是查看<em>(m+1)</em>*<em>(n+1)</em>节点的有向无环图。通过此图的每条路径(从左上到右下)表示匹配单词的唯一方式。我们希望匹配字符串,并在单词中添加空格(<code>-</code>),以便它们与最大数量的常用字母对齐。例如<code>cay</code>和<code>ayc</code>的结束状态将是</p>
<pre><code>cay-
-ayc
</code></pre>
<p>每个节点为其表示的部分匹配存储最高数量的匹配,并且在算法结束时,结束节点将为我们提供最高数量的匹配</p>
<p>我们从左上角开始,在这里没有匹配的字母,所以这里有0个匹配的字母(分数0)</p>
<pre><code> c a y
0 . . .
a . . . .
y . . . .
c . . . .
</code></pre>
<p>我们将遍历此图,并使用以前节点的数据计算每个节点的最大匹配字母数</p>
<p>节点连接在左侧->;右,向上->;向下和斜向左向上->;马上下来</p>
<ul>
<li>向右移动表示使用<code>cay</code>中的一个字母,并将我们到达的字母与插入<code>ayc</code>中的<code>-</code>匹配</李>
<li>向下移动表示相反的情况(从<code>ayc</code>消费,并将<code>-</code>插入到<code>cay</code>)</李>
<li>对角移动表示从每个单词中抽取一个字母并匹配这些字母</李>
</ul>
<p>查看起始节点右侧的第一个节点,它表示匹配</p>
<pre><code>c
-
</code></pre>
<p>这个节点(显然)只能从起始节点到达</p>
<p>第一行和第一列中的所有节点都将为0,因为它们都表示匹配一个或多个具有相同数量<code>-</code>的字母</p>
<p>我们得到了图表</p>
<pre><code> c a y
0 0 0 0
a 0 . . .
y 0 . . .
c 0 . . .
</code></pre>
<p>这就是设置,现在有趣的部分开始了</p>
<p>查看第一个未赋值的节点,它表示将子字符串<code>c</code>与<code>a</code>进行匹配,我们想确定如何使用最多数量的匹配字母到达该节点</p>
<ul>
<li>备选方案1:我们可以从左边的节点到达那里。左侧的节点表示匹配的节点</li>
</ul>
<pre><code>-
a
</code></pre>
<p>因此,通过选择这条路径到达当前节点,我们就到达了</p>
<pre><code>-c
a-
</code></pre>
<p>将<code>c</code>与<code>-</code>匹配不会给出正确的匹配,因此此路径的分数为0(取自上一个节点)加0(刚刚进行的匹配<code>c/-</code>的分数)。因此,对于这个路径,0+0=0</p>
<ul>
<li>备选方案2:我们可以从上面到达该节点,该路径表示从</li>
</ul>
<pre><code>c -> c-
- -a
</code></pre>
<p>这也给了我们额外的0分。这个分数是0</p>
<ul>
<li>备选方案3:我们可以从左上角到达该节点。这是从起始节点(完全没有)移动到从每个字母消耗一个字符。这就是匹配</li>
</ul>
<pre><code>c
a
</code></pre>
<p>因为<code>c</code>和<code>a</code>是不同的字母,所以这个路径也得到了0+0=0</p>
<pre><code> c a y
0 0 0 0
a 0 0 . .
y 0 . . .
c 0 . . .
</code></pre>
<p>但是对于下一个节点,它看起来更好。我们仍有三个备选方案需要考虑。
备选方案1&;2总是给我们额外的0分,因为它们总是表示用<code>-</code>匹配一个字母,所以这些路径将给我们0分。让我们转到备选方案3</p>
<p>对于我们当前的节点,对角移动意味着从</p>
<pre><code>c -> ca
- -a
</code></pre>
<p><strong>这是一场比赛</强></p>
<p>这意味着有一条到这个节点的路径给我们1分。我们扔掉0,保存1</p>
<pre><code> c a y
0 0 0 0
a 0 0 1 .
y 0 . . .
c 0 . . .
</code></pre>
<p>对于此行的最后一个节点,我们查看了三个备选方案,并意识到我们不会获得任何新的点(新的匹配),但我们可以使用之前的1点路径到达节点:</p>
<pre><code>ca -> cay
-a -a-
</code></pre>
<p>所以这个节点的得分也是1</p>
<p>对所有节点执行此操作,我们将得到以下完整的图</p>
<pre><code> c a y
0 0 0 0
a 0 0 1 1
y 0 0 1 2
c 0 1 1 2
</code></pre>
<p>分数增加的唯一原因是什么</p>
<pre><code>c -> ca | ca -> cay | - -> -c
- -a | -a -ay | y yc
</code></pre>
<p>所以末端节点告诉我们最大匹配是2个字母。
因为在您的案例中,您希望知道分数为2的最长路径,所以您需要跟踪每个节点的路径</p>
<p>此图很容易实现为矩阵(或数组数组)</p>
<p>我建议您作为元素使用一个<code>tuple</code>和一个<code>score</code>元素和一个<code>path</code>元素,在path元素中只存储对齐字母,那么最终矩阵的元素将是</p>
<pre><code> c a y
0 0 0 0
a 0 0 (1, a) (1, a)
y 0 0 (1, a) (2, ay)
c 0 (1, c) (1, a/c) (2, ay)
</code></pre>
<p>在一个地方我注意到<code>a/c</code>,这是因为字符串<code>ca</code>和<code>ayc</code>有两个不同的最大长度的子序列。在这些情况下,您需要决定要做什么,要么选择一个,要么两个都保存</p>
<p><strong>编辑:</strong></p>
<p>下面是此解决方案的一个实现</p>
<pre><code>def longest_common(string_1, string_2):
len_1 = len(string_1)
len_2 = len(string_2)
m = [[(0,"") for _ in range(len_1 + 1)] for _ in range(len_2 + 1)] # intitate matrix
for row in range(1, len_2+1):
for col in range(1, len_1+1):
diag = 0
match = ""
if string_1[col-1] == string_2[row-1]: # score increase with one if letters match in diagonal move
diag = 1
match = string_1[col - 1]
# find best alternative
if m[row][col-1][0] >= m[row-1][col][0] and m[row][col-1][0] >= m[row-1][col-1][0]+diag:
m[row][col] = m[row][col-1] # path from left is best
elif m[row-1][col][0] >= m[row-1][col-1][0]+diag:
m[row][col] = m[row-1][col] # path from above is best
else:
m[row][col] = (m[row-1][col-1][0]+diag, m[row-1][col-1][1]+match) # path diagonally is best
return m[len_2][len_1][1]
</code></pre>
<pre><code>>>> print(longest_common("hcarry", "sallyc"))
ay
>>> print(longest_common("cay", "ayc"))
ay
>>> m
[[(0, ''), (0, ''), (0, ''), (0, '')],
[(0, ''), (0, ''), (1, 'a'), (1, 'a')],
[(0, ''), (0, ''), (1, 'a'), (2, 'ay')],
[(0, ''), (1, 'c'), (1, 'c'), (2, 'ay')]]
</code></pre>