我实现了两个迈尔斯版本的 diff 算法，第一个是贪婪算法（可行，但在内存消耗方面是高度资源密集型的 - 但迈尔斯已经在他的论文中写到了），然后是精炼版本。
但是，对于像 lcs(»xx«, »x«) 这样的简单输入，这会失败。
据我了解，原因是它试图找到的常见蛇是不明确的：让我们用“L[...]«”来标记“左蛇”，用“R[...]”来标记“蛇”正确的蛇«来区分它们。当前进到步骤 d = 0 时，算法检测到这条蛇：»L[x]x«->»L[x]«。现在，在相反的步骤中，算法检测到这条蛇：»xR[x]«->»R[x]«。在向前 d = 1 步骤中，算法找到秒（空）蛇，产生： »L[x]xR[]«->L[x]R[]« 并在后退步骤中找到 »L[]xR [x]«->L[]R[x]«.
如您所见，两个方向的 x 匹配都会找到第一个可能的蛇，但在正向情况下，它是 L[x]，但在反向情况下，它是 R[x]。
所以这个算法没有找到有效的普通蛇。
在引理 3 中，迈尔斯证明，如果存在从 (0,0) 到 (n,m) 的 D 路径，则必须存在从 (0,0) 到某个 (x,y) 的 D/2 路径) 和从 (x,y) 到 (n,m) 的 D/2 路径。我将跳过证明，因为很明显，您可以在任何“有效”点处切割 D 路径以获得两条较短的路径，它们组合回一条 D 路径，并且您可以只取中间的路径D 路径的切割部分。无论如何：他确实证明了这样一个 (x,y) 对的存在（实际上，他通过添加第二点 (u,v) 证明了这一点更复杂一些 - 但为了理解我的问题，这并不真正问题），但是（根据我的理解）他没有证明，使用他的算法，你一定能找到 D 路径的任何可能的切点 (x,y) 和 (u,v)。
如上所示，我相信，Myers 的精炼算法实际上无法找到 »xx«->»x« 的解。
我在这里错过了一些重要的事情吗？
我在这里错过了一些重要的事情吗？
是的 - 迈尔斯定义“重叠”的方式是他的算法实际上根本不需要你所谓的“普通蛇”。
回想一下这是算法：
∆ ← N−M
For D ← 0 to ⌈(M+N)/2⌉ Do
For k ← −D to D in steps of 2 Do
Find the end of the furthest reaching forward D-path in diagonal k.
If ∆ is odd and k ∈ [∆−(D−1),∆+(D−1)] Then
If the path overlaps the furthest reaching reverse (D − 1)-path in diagonal k Then
Length of an SES is 2D−1.
The last snake of the forward path is the middle snake.
For k ← −D to D in steps of 2 Do
Find the end of the furthest reaching reverse D-path in diagonal k+∆.
If ∆ is even and k + ∆ ∈ [−D,D] Then
If the path overlaps the furthest reaching forward D-path in diagonal k+∆ Then
Length of an SES is 2D.
The last snake of the reverse path is the middle snake.
在您的示例中，旧文本为“xx”，新文本为“x”，我们有一个宽度为 3 x 高度为 2 的编辑图，N = 2，M = 1，Δ = 1（这是奇数）。
我们开始算法的最外层循环。当 D=0 时，正如您所注意到的，前向路径从 (0, 0) 对角移动到 (1, 1)，然后反向路径从 (2, 1) 对角移动到 (1, 0)。
接下来我们考虑D=1。按照算法的指示，first我们考虑将forward-reaching路径扩展到对角线-1和1上。当我们考虑对角线1时，我们发现我们可以水平移动到它，从(1, 1)移动到(2, 1)。正如您所注意到的，我们现在已经到达编辑图的末尾，并且该对角线上没有“常见”蛇；该对角线上最远反向路径的最后一条蛇从 (2, 1) 到 (1, 0)，而 forward 路径的最后一条蛇是从 (2, 1) 到 (2, 1) 的空蛇).
但是，该算法不需要普通的蛇。相反，我们检查...
如果 Δ 为奇数且 k ∈ [Δ−(D−1),Δ+(D−1)]
（是的，是的）
然后 如果路径与对角线 k 中最远到达的反向 (D − 1) 路径重叠 SES 的长度是 2D−1。 前进路径的最后一条蛇是中间的蛇。
这里的“重叠”是什么意思？它在前面的引理 3 中被定义；结束于 (x, y) 的正向路径被称为“重叠”结束于 (u, v) 的反向路径，如果：
x−y = u−v 且 x ≥ u。
我们在对角线 1 上的正向和反向路径端点 - 分别为 (2, 1) 和 (1, 0) - 事实上满足这个定义，即使蛇只是接触一个顶点并且不会“重叠”具有一些共同点的（可能更直观的）感觉。事实上，根据迈尔斯的定义，它们可以“重叠”而不接触，就像你将“x”与“xxx”进行比较时的情况一样。
因此我们现在有实际上找到了一条从(2, 1)到(2, 1)的（空的）“中蛇”，并且中蛇算法成功了。