问题标签 [lcs]

我有两个字符串，长度相同。我必须检查它们是否可以表示为 XYZ 和 XZY，其中 Y 和 Z 不为空。

我的解决方案是“吃掉”两个字符串的相同首字母，然后找到最长的公共子字符串进行休息。然后检查第一个字符串的其余部分和第二个字符串的其余部分（没有 LCS）是否相等。问题是，我听说过 O(N) 内存复杂度算法，但我发现的只是 O(MN)。我的记忆力有限，所以这对我很重要。

第二种解决方案是使用 "(.*)(.+)(.+)\1\3\2" 正则表达式，但这是非常糟糕的解决方案。

有人有其他想法吗？

我需要将源字符串转换为目标字符串，并表达与对源字符串的操作 (D,A,TYPE) 即（删除、添加、PREFIX\SUFFIX）相同的操作，这将在应用这些操作时将其转换为目标字符串源字符串的后缀，或源字符串的前缀

例如：

以下代码确实获得了后缀，但也获得了所有其他匹配项，但我只需要后缀，除此之外它不会按照我的要求输出正确的格式。

此外，如果没有足够的后缀/前缀匹配，我也不需要输出任何更正，例如：字符串足够，超出不应该产生匹配，这可能来自：

我正在尝试绘制 LCS 表。我的这部分代码在fill_the_table()函数内部 while 循环的第一次迭代后停止。我找不到我的代码有什么问题。顺便说一句，我是 C++ 新手...

1. 我可以通过从到的方式int** table和方式吗？int** ptable()fill_the_table()
2. 有人建议我使用vector<string>而不是自己阅读文件，哪个更可取？

我试图理解Hunt & McIlroy的算法，但我不明白如何找到k-candidates。

我知道k-candidates是成对的索引，例如：

• A_i = B_j
• P_(ij) > max(P_(i-1, j), P_(i, j-1))

第二点暗示了k-candidates的两个属性：

在文件A的前i行和文件B的前j行中有一个长度为k的公共子序列。对于文件A 的i 行或文件B的j行，没有长度为k的公共子序列。

现在我如何得到纸上的图片？k-候选人是什么？一旦他们找到他们，我就将他们联合起来？

我也在维基百科上搜索过，但它更清楚..谢谢

上述程序用于使用动态规划找到最大公共子序列解决方案。我能够计算 LCS 的长度，但我无法推断找到总数的逻辑。系统将进行比较以找到 lcs 。

我想找到总数。比较并使用全局计数变量打印它。有人可以帮我吗？

关于它们是如何工作的，我想知道低级的工作内容：

1. 什么会触发合并冲突？
2. 工具是否也使用上下文来应用补丁？
3. 他们如何处理实际上并未修改源代码行为的更改？例如，交换函数定义位置。

关于安全性，说实话，庞大的 Linux 内核存储库证明了它们的安全性。但我想知道以下几点：

1. 关于用户应该注意的工具是否有任何警告/限制？
2. 算法是否被证明不会产生错误的结果？
3. 如果没有，是否有建议集成测试的实现/论文至少证明它们在经验上是无错误的？类似于BrianKorver和JamesCoplien这些论文的内容。
4. 同样，Linux 存储库就前一点来说应该足够了，但我想知道一些更通用的东西。源代码，即使改变了，也不会改变太多（特别是因为实现的算法和语法限制），但是安全性可以推广到通用文本文件吗？

编辑

好的，我正在编辑，因为问题含糊不清，答案没有解决细节。

Git/diff/补丁详细信息

Git 似乎默认使用的统一差异格式基本上输出三件事：更改、更改周围的上下文以及与上下文相关的行号。这些事情中的每一项都可能同时发生变化，也可能不会发生变化，因此 Git 基本上必须处理 8 种可能的情况。

例如，如果在上下文之前添加或删除了行，则行号将不同；但是如果上下文和更改仍然相同，则 diff 可以使用上下文本身来对齐文本并应用补丁（我不知道这是否确实发生）。现在，其他情况会发生什么？我想知道 Git 如何决定自动应用更改以及何时决定发出错误并让用户解决冲突的详细信息。

可靠性

我很确定 Git 是完全可靠的，因为它确实有完整的提交历史并且可以遍历历史。我想要的是一些关于这方面的学术研究和参考的指针，如果它们存在的话。

仍然与这个主题有点相关，我们知道 Git/diff 将文件视为通用文本文件并在行上工作。此外，diff 使用的 LCS 算法将生成一个补丁，以尽量减少更改的数量。

所以这里有一些我也想知道的事情：

1. 为什么使用 LCS 而不是其他字符串度量算法？
2. 如果使用 LCS，为什么不使用考虑到底层语言语法方面的度量标准的修改版本？
3. 如果使用这种考虑到语法方面的指标，它们能带来好处吗？在这种情况下，好处可以是任何东西，例如，更干净的“责备日志”。

同样，这些可能是巨大的主题，欢迎学术文章。

问题是找到任何给定数组的 LIS（最长递增子序列）。前任。a[]={10,9,7,8,9}; 长度=3；{7,8,9}

所以在 nlogn 中做的一种方法是

1. 对数组进行排序
2. 取LCS的两个Resulting就是LIS。

现在我明白了该怎么做。但是我如何证明它是正确的。如何在这里申请 MI？

我们在秋季学期学习了动态规划理论，我正在努力复习并继续进一步研究它。我目前正在尝试一种天真的方法来解决此 TopCoder 文章中提到的 LCS 问题：动态编程

算法如下：

例如，给定字符串“ABCDE”和“DACACBE”，最长的公共子序列是“ACE”。

但是，我的输出是有效的子字符串“ABE”而不是正确的“ACE”。我的实施顺序有什么问题？

我不明白O(2^n)最长公共子序列算法的递归函数的复杂性。

通常，我可以将此表示法与算法的基本操作（在本例中为比较）的数量联系起来，但这一次在我看来没有意义。

例如，有两个长度相同的字符串5。在最坏的情况下，递归函数计算251比较。2^5甚至不接近那个值。

谁能解释这个函数的算法复杂性？

是否有（容易）识别两个字符串共享的共同模式的可能性？这里有一个小例子来说明我的意思：

我有两个包含字符串的变量。两者都包括相同的模式（“ABC”）和一些“噪音”。

假设我不知道常见模式，我希望 R 找出两个字符串都包含“ABC”。我怎样才能做到这一点？

*编辑

第一个例子可能有点简单化。这是我真实数据中的一个例子。

两个字符串都包含我希望函数识别的“DUISBURG”。

*编辑

我采用了评论中发布的链接中提出的解决方案。但我仍然没有我想要的。

如果函数正在寻找两个向量的最长公共子序列，为什么它不会在 之后停止"D" "U" "I" "S" "B" "U" "R" "G"？.