我正在使用 LCS 算法在 c++ 中实现我自己的差异。在查看 LCS 算法论文并试图找到 SES（最短编辑脚本）时，有时会出现一行更改。在下面的图形示例中，它仅显示插入和删除。因此，向后遍历图形，水平线是删除，垂直线是插入。您有“c”更改案例的情况是什么？我假设它将是一条水平线，然后是一条垂直线，即：删除然后插入将被视为更改。我还没有看到任何直接创建 SES 的 C++ 代码。也许有一个更好的实现可以获得 O(ND) 或更好的时间复杂度，尽管我不确定如何在不创建和反转图形的情况下创建 SES。我可以实现 LCS 构建图形并将其遍历回来我只是想提前知道创建 SES 的确切规则是什么，因为在这种情况下你可能需要维护 2 个状态删除和插入被视为行变化）？请参阅以下文件，您可以在其中获得更改 3、4c4、6（见下文）。如果有人有任何示例代码正在执行此操作，以便最大化 C++ 中的运行时间与空间，这将有助于作为参考，尤其是在以如下所示的当前 diff 二进制形式创建 diff 输出方面。我使用这个版本是因为我正在最大化运行时间并为此牺牲空间。s 创建 SES 的确切规则，因为在这种情况下，您可能需要维护 2 个状态，删除和插入被视为行更改？请参阅以下文件，您可以在其中获得更改 3、4c4、6（见下文）。如果有人有任何示例代码正在执行此操作，以便最大化 C++ 中的运行时间与空间，这将有助于作为参考，尤其是在以如下所示的当前 diff 二进制形式创建 diff 输出方面。我使用这个版本是因为我正在最大化运行时间并为此牺牲空间。s 创建 SES 的确切规则，因为在这种情况下，您可能需要维护 2 个状态，删除和插入被视为行更改？请参阅以下文件，您可以在其中获得更改 3、4c4、6（见下文）。如果有人有任何示例代码正在执行此操作，以便最大化 C++ 中的运行时间与空间，这将有助于作为参考，尤其是在以如下所示的当前 diff 二进制形式创建 diff 输出方面。我使用这个版本是因为我正在最大化运行时间并为此牺牲空间。
请参阅文档的第 3 页及其示例图表，其中显示了图表的 SES 反转
http://www.xmailserver.org/diff2.pdf
我在 linux 上使用常规差异的更改差异示例
fileA.txt
a
b
c
d
e
f
g
fileB.txt
w
a
b
x
z
y
e
diff fileA.txt fileB.txt
0a1
> w
3,4c4,6
< c
< d
---
> x
> z
> y
6,7d7
< f
< g