问题标签 [lcs]

这行得通，但 valgrind 大声抱怨无效读取。我是怎么弄乱记忆的？对不起，我总是在 C 内存分配上失败。

我们可以使用 DP（动态规划）找到两个字符串的 LCS（最长公共子序列）。通过跟踪 DP Table 我们可以获得 LCS。但是，如果存在不止一个 LCS，我们如何才能获得所有这些 LCS？

例子：

这里的“ab”和“bc”都是LCS。

我有这段代码，它计算随机字符串之间的最长公共子序列，以查看如何准确地重建输入的未知区域。为了获得好的统计数据，我需要对其进行多次迭代，但我当前的 python 实现太慢了。即使使用pypy，它目前也需要 21 秒才能运行一次，理想情况下我希望运行 100 次。

我尝试将它转换为 numpy，但我一定做得很糟糕，因为它实际上运行得更慢。这段代码能以某种方式加速吗？

更新。在下面的评论之后，如果直接使用循环会更好，它会在相同长度的所有子列表lcses之间给出 LCS 。是否有可能以某种方式修改经典的动态编程 LCS 算法来做到这一点？patterntext

我正在开发 web 应用程序的一部分，用户将能够一起更改同一个文件并查看彼此所做的更改（就像 Google Drive 目前所做的那样）。但我坚持“查看彼此所做的更改”和合并文件部分。

我看过这篇文章：如何在 PHP 或 JavaScript 中合并文件的两个版本？而且我已经了解如何在文件的两个部分之间找到 le LCS。但是我不知道在此之后该怎么办......当我得到 LCS 时，我将拥有三个文件（我的、其他用户的和原始文件）之间相同的部分，但接下来要做什么?

我不能在这方面使用任何像 SVN 这样的系统，因为会有太多的提交/更新来让每个用户的浏览器保持最新。

你有什么线索吗？

谢谢 ！

我正在使用 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 上使用常规差异的更改差异示例

如何显示两个子串的最长公共子串的所有子串我知道计算 lcs 长度的 dp 方法但是如何显示 lcs 的所有这些 lcs 代码

我在网上找不到一篇关于如何找到所有 lcs 的好文章

字符串 1=abcabcaa 字符串 2=acbacba

所有 lcs

ababa abaca abcba

我已经知道计算 lcs 的 dp 方法，任何帮助将不胜感激

我在维基上找到了这个

但我很难理解它

如何在更大的字符串（600000 个字符）上应用最长的公共子序列。有没有办法在 DP 中做到这一点？我已经为较短的字符串做到了这一点。

我是这个 ERLANG 的新手，我知道基础知识。这就像计划，但更广泛。我知道如何创建一个函数，但我在创建一个获取最长公共子序列的函数时遇到了问题。

lcs(str1,str2)是一个接受两个字符串并输出一个整数的函数：

lcs(algorithm,logarithm)将输出7，因为可以制作的最长公共子序列lgrithm是7大小。

非常感谢任何答案。

我知道一般的 LCS 问题和算法。

就像这样：

但是如果我们添加一个间隙条件呢？

例如：

视觉表现：

我该如何解决这个问题？

如何制作 DP 表？

假设有许多已知是由单个模板生成的文本（例如，许多 HTML 页面，由某种数据库中的数据支持的模板呈现）。一个非常简单的例子：

仅给定这 3 个文本，我想获得如下所示的原始模板：

以及与此模板一起使用的 3 组字符串：

• $1 = 937, $2 =alice
• $1 = 28, $2 =bob
• $1 = 925931, $3 =charlie

换句话说，“模板”是所有给定文本中遇到的公共子序列的列表，总是以一定的顺序出现，除了这些子序列之外的所有其他内容都应该被视为“数据”。

我猜一般算法将与任何 LCS（最长公共子序列）算法非常相似，尽管使用不同的回溯代码，它会以某种方式将“模板”（所有给定文本的通用字符）和“数据字符串”（不同字符）分开。

额外的问题：有现成的解决方案吗？