algorithm - Myers算法的终点

我试图理解myers关于问题LCS/ses（shortest edit script）的算法，但是不理解终点是什么，然后不理解我们如何继续使用算法。
有人知道怎么解释吗？
这里有一些链接，一个在paper by Myers上，另一个在"summary"上（做得很好）。
提前感谢大家

最佳答案

LCS/SES算法

Constant MAX ∈ [0,M+N]
Var V: Array [− MAX .. MAX] of Integer

V[1] ← 0
For D ← 0 to MAX Do
    For k ← −D to D in steps of 2 Do
        If k = −D or k ≠ D and V[k − 1] < V[k + 1] Then
            x ← V[k + 1]
        Else
            x ← V[k − 1]+1
        y ← x − k
        While x < N and y < M and a x + 1 = b y + 1 Do (x,y) ← (x+1,y+1)
        V[k] ← x
        If x ≥ N and y ≥ M Then
            Length of an SES is D
            Stop
Length of an SES is greater than MAX

定义
d-path这是一条从(0, 0)开始的路径，使用的是D非对角边，即垂直或水平边。
k-对角线-这是由所有点组成的对角线(x, y)，因此x-y=k
仅由对角边组成的蛇形路径
我们在V中存储什么V[k]存储k对角线上最远到达路径端点的行索引。路径应该从(0, 0)开始。
我们为什么要这么做？请记住，我们希望找到从(0, 0)到(N, M )的路径，该路径使用最少的水平和垂直边。因此，在某种意义上，我们正在寻找最小值，这样就有一个以D结尾的D-path。
终点指的是什么？它是指a(N, M)的最后一点我们特别关注沿每条对角线最远的终点
假设我们已经计算了所有D-path，k的V。要为所有D-paths，D<=D'-1更新，我们使用以下事实：
最远到达对角线K罐上的D-路径
一般分解为最远到达（D-1）路径
对角线K-1，后接水平边，后接最长边
可能是蛇，也可能被分解成最远的一条（D-）
1）-对角线k+1上的路径，后跟垂直边，然后是
最长的蛇。