问题标签 [lcs]

我正在尝试计算两个字符串之间存在的最长可能子序列的数量。

例如字符串 X = "efgefg"; 字符串 Y = "efegf";

输出：最长公共序列的数量为：3（即：efeg, efef, efgf - 这个不需要算法计算，这里只是为了演示）

我已经设法在 O(|X|*|Y|) 中使用基于这里的一般思想的动态编程来做到这一点：最便宜的路径算法。

任何人都可以想出一种方法来有效地进行更好的运行时间计算吗？

——针对 Jason 的评论进行了编辑。

我在 Flex/AS3 中工作（为简单起见）一个 XML 编辑器。我需要提供撤消/重做功能。

当然，一种解决方案是在每次编辑时存储整个源文本。但是，为了节省内存，我想存储差异（这些差异也将用于将更新传输到服务器以进行自动保存）。

我的问题是 - 我可以使用纯文本差异算法来跟踪这些 XML 更改吗？

我在互联网上的研究表明我不能这样做。但是，我显然错过了一些东西。明文 diff 提供的功能据称是：

XML 只是文本，那么为什么我不能只使用 diff() 和 patch() 来可靠地转换文本呢？

例如：假设我是一个诗人。当我写诗时，我会使用很多时髦的标点符号……你知道，像 <、/ 和 >。（您可能会看到我将如何处理...）如果我在使用差异来提供撤消/重做功能的应用程序中写诗，那么当我撤消/重做我的编辑时，我的诗歌会变得乱码吗？这只是文字！为什么它会对算法产生影响？

我显然在这里没有得到任何东西......感谢您的解释！:)

更新：

我遇到的一些关于使用纯文本算法区分 XML 的讨论：

• http://code.google.com/p/google-diff-match-patch/wiki/Plaintext
• 是否有一个针对 htmlstring 的 JS diff 库，就像纯文本上的 google-diff-match-patch 一样？

另外，我知道命令模式可能是实现撤消/重做的更好方法。为了简单起见，我已经简化了我的用例，我仍然认为 XML diffing 是最好的方法。

我有两个非常大的字符串，我正在尝试找出它们的Longest Common Substring。

一种方法是使用后缀树（假设具有非常好的复杂性，尽管实现复杂），另一种是动态编程方法（以上链接的维基百科页面都提到了这两种方法）。

使用动态规划

问题是动态规划方法的运行时间很长（复杂度是O(n*m), wheren和m是两个字符串的长度）。

我想知道的（在开始实现后缀树之前）：如果我只想知道公共子字符串的长度（而不是公共子字符串本身），是否可以加快算法速度？

考虑 2 个序列 X[1..m] 和 Y[1..n]。记忆算法将在 O(m*n) 时间内计算 LCS。有没有更好的算法来找出 LCS wrt time？我猜对角线的记忆可以给我们 O(min(m,n)) 时间复杂度。

我正在寻找用于 C++ 程序的 LCS 算法的（空间）高效实现。输入是两个随机访问整数序列。
我目前正在使用关于 LCS 的维基百科页面中的动态编程方法。但是，这在内存和时间上有 O(mn) 的行为，并且在我身上死掉了，因为更大的输入会出现内存不足的错误。
我已经阅读了 Hirschberg 的算法，它可以显着提高内存使用率，Hunt-Szymanski 以及 Masek 和 Paterson。由于实现这些并非易事，我更愿意使用现有实现在我的数据上尝试它们。有人知道这样的图书馆吗？我想既然文本差异工具很常见，应该有一些开源库吗？

我在 C 中实现最长公共子序列问题。我希望比较执行解决方案的递归版本和动态编程版本所花费的时间。如何找到在两个版本中针对各种输入运行 LCS 功能所花费的时间？我还可以使用 SciPy 在图表上绘制这些值并推断时间复杂度吗？

提前致谢，

剃刀

对于递归和动态编程方法中的最长公共子序列问题，我希望根据输入大小绘制时间。到目前为止，我已经开发了两种方式来评估 lcs 函数的程序，一个简单的随机字符串生成器（在此处的帮助下）和一个绘制图形的程序。现在我需要通过以下方式连接所有这些。

现在我必须连接所有这些。也就是说，计算 lcs 的两个程序应该运行大约 10 次，并将简单随机字符串生成器的输出作为这些程序的命令行参数给出。

计算执行这些程序所花费的时间，并将其与使用的字符串长度一起存储在一个文件中，例如

这由 python 程序解析以填充以下列表

然后绘制图表。关于上述问题，我有以下问题。

1) 如何将一个 C 程序的输出作为命令行参数传递给另一个 C 程序？

2) 是否有任何函数可以评估执行函数所需的时间（以微秒为单位）？目前我唯一的选择是unix中的时间函数。作为一个命令行实用程序使其更难处理。

任何帮助将非常感激。

我已经实现了一个未压缩的后缀树。我想知道如何解决在字符串中查找最长重复子字符串的问题。我知道我们必须找到有两个孩子的最深的内部节点，但是如何编码。另外，我们如何知道最长的重复子串是什么。我对 JAVA 中的代码很感兴趣。请给出java实现。作为参考，我的 TrieNode 看起来像

我试图找到 3 个或更多字符串的最长公共子序列。Wikipedia 文章很好地描述了如何为 2 个字符串执行此操作，但我有点不确定如何将其扩展到 3 个或更多字符串。

有很多库可以找到 2 个字符串的 LCS，所以如果可能的话，我想使用其中一个。如果我有3个字符串A，B和C，找到A和B的LCS作为X是否有效，然后找到X和C的LCS，或者这是错误的方法吗？

我在 Python 中实现了如下：

这输出“ba”，但它应该是“baa”。

我正在尝试用 C++ 创建一个能够区分两个 .txt 文件的程序。

如您所见，我有两个缓冲区（行向量）以前加载了文件内容。我还有 LCS 算法功能齐全（经过测试）。LCS 适用于全局定义的字符串 X 和 Y。

所以，我真正需要做的是逐行比较缓冲区和 LCS，但我没有办法做到这一点。

请你帮助我好吗？