我正在尝试了解有关问题 LCS 的 Myers 算法/SES(最短编辑脚本)，但不了解终点 是什么，也不了解我们如何处理该算法。 有人知道怎么解释吗？
这里有链接，一个在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-diagonal - 这是由所有点组成的对角线 (x, y)这样 x-y=k
蛇形 - 仅由对角线边缘组成的路径
我们在 V 中存储了什么？ ？ V[k]存储 k 对角线上最远到达路径端点的行索引。该路径应从 (0, 0) 开始.
我们为什么要这样做？请记住，我们要从 (0, 0) 中找到路径至 (N, M )它使用最少的水平和垂直边缘。所以从某种意义上说，我们正在寻找最小 D这样就有一个D-path以 (N, M) 结尾
终点指的是什么？它指的是 D-path 的最后一点.我们尤其对沿每个 k 到达的最远端点感兴趣。 -对角线
假设我们计算了V对于所有 D-paths , D<=D'-1 .为所有更新D-paths , D<=D'我们使用事实:
A furthest reaching D-path on diagonal k can without loss of generality be decomposed into a furthest reaching (D − 1)-path on diagonal k − 1, followed by a horizontal edge, followed by the longest possible snake or it may be decomposed into a furthest reaching (D − 1)-path on diagonal k+1, followed by a vertical edge, followed by the longest possible snake.
关于algorithm - Myers 算法的终点，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/33054560/