问题标签 [lcs]

我想创建一个蛮力算法来找到 2 个字符串之间的最大公共子序列，但我正在努力以算法的形式枚举所有可能性。

我不想要一个动态编程的答案，奇怪的是我设法弄清楚了这个（你会认为蛮力方法会更容易）。请使用伪代码，因为我更喜欢自己理解并编写它。

我写了一个算法，它找到两个字符串的最长公共子序列。

以下是“plik1”文件包含的内容：

这是应该保存在file2中的内容：

编译后出现错误：

我不知道，代码有什么问题......

给定 2 个字符串，我们必须找到一个长度最小的字符串，使得给定的字符串是该字符串的子序列。换句话说，我们需要找到一个字符串，以便删除一些字符会产生给定的字符串。一直在想蛮力和LCS，但徒劳无功。

12345 和 11234 应该导致 112345 WWA 和 WWS 有一个答案 WWAS

LCS 的内存效率非常低（DP 之一），蛮力只是幼稚。我应该怎么办？

我已经写了LCS的部分。
我想知道如果我给 N(N>3) ，那意味着有多少组输入。
像这样：
输入：
4 ab abc abcd abcde
输出：
3
找到最长的那些 lcs（3 个序列一个部分）
ab abc abcd->ab->2
abc abcd abcde->abc->3
3>2
我的想法是每组数只用3个序列的方式，然后找到最大的一个。
但我不知道该怎么做或有更好的方法？
这是我的代码的一部分：

LCS：

谢谢大家~我已经通过使用二维数组来存储序列解决了这个问题。

我有一个关于在 R 中查找最长公共子字符串的问题。在搜索 StackOverflow 上的一些帖子时，我了解了 qualV 包。但是，我看到这个包中的 LCS 函数实际上找到了 string1 中存在于 string2 中的所有字符，即使它们不连续。

解释一下，如果字符串是 string1 : " hell lo" string2 : " hel 12345lo" 我希望输出是hel，但是我得到的输出是 hello。我一定做错了什么。请在下面查看我的代码。

我也尝试了 Rlibstree 方法，但我仍然得到不连续的子字符串。此外，子字符串的长度也超出了我的预期。请参见下文。

我正在寻找一个 java util，它可以在两个 java 对象之间创建差异，可以嵌套并包含数组等。该 util 还应该能够在原始对象上应用差异（又名补丁）并删除差异从中。

我在 JS 中得到了一个：https ://github.com/benjamine/jsondiffpatch 。但是，如果 Java 中已经存在一个，那就太好了。

另请注意，该工具应实现 LCS，并且数组比较应基于散列函数（可自定义）而不是逐字（逐行）比较，这意味着它应处理数组移动等。

Diff 可以采用 XML/JSON 转换的 java 对象

所以我一直在为 Perl 和 Python 做一些练习题（在两者之间进行选择），我遇到了一个问题，我需要像 Github 一样制作自己的差异算法。我已经知道最长公共子序列问题是解决方案的重要组成部分。我使用LCS 的维基百科页面作为参考，但我仍然无法找出差异部分。

我也意识到 CPAN 上已经有像 Algorithm:Diff 这样的模块，但这主要是为了练习，那些感觉像是在作弊。

我想出了算法的python/伪代码版本，但我打算用多维数组来做，而Perl似乎没有。

现在我可以在 Perl 中成功获得最长公共子序列长度了。

基本上我能想到的伪代码（几乎类似于 python，但应该用于 Perl）是这样的：

我还没有实现它，但我认为这基本上就是我可以计算两个字符串的 LCS 长度的方法？

输出明智，它应该针对“人类”和“黑猩猩”（LCS = HMAN）返回 4

所以我要问的是，从现在开始，我如何才能使用 Perl 打印 Diffs？我知道，我应该返回一个列表/数组，而不是只返回 LCS 的长度，这可以通过在 LCS 函数中返回一个多维列表，然后稍后在单独的 diff 函数中处理它来实现.

我对 Perl 有点陌生，所以任何指针/提示将不胜感激。谢谢。

函数 print_lcs 从 m,n 开始，用于打印子序列。lcs 函数将找到 lcs 的两个 d 数组 b 有字符 C,U,L 表示左上、上和左元素。我得到的输出不是答案，它给出的子序列比实际答案短。

对于输入 seq 1= 1000101011& seq 2=00011101我得到 lcs as001而实际答案是0001101

我有 3 个文件，每个文件大小约为 6MB，我需要知道这些文件中常见的块是什么。对于块，我的意思是 128 字节长的二进制数据块。不幸的是，它们可能从任何地方开始。我需要知道，这些块出现在文件中的什么位置。我已经阅读了一些关于最长公共序列问题的文本，但我的问题有点不同，因为我不需要 2 个文件中最长的文件，但 3 个文件中的所有文件都合理。这些块没有对齐，所以一个 128 字节的块可能从任何地方开始。我很确定这很复杂，但也许有人知道这个问题的聪明解决方案，最好是使用现有的工具。

我对如何编写最愚蠢的版本有一个模糊的想法（将所有内容与所有内容进行比较），但我需要在本世纪得到一个结果；）

有没有办法在 O(NlogN) 时间内找到两个序列的最长公共子序列？

我在某处读到有一种方法可以使用二进制搜索来实现这一点。

我知道需要 O(N ² ) 时间的 dp 方法。