问题标签 [lcs]

您好，我是 c 新手，我在运行代码时遇到了一些问题，一切编译正常，但是当我输入第一个输入时，exe 崩溃。我很确定问题出在数组的内存分配或指针的使用上，但我似乎无法弄清楚问题所在。

这是我的2个文件。

主程序

lcs.c

场景：给定 2 个输入字符串，我需要找到将一个字符串转换为另一个字符串所需的最小插入删除和替换次数。字符串是来自 2 个文件的文本。比较必须在单词级别进行。

我所做的是实现了编辑距离算法，该算法使用大小为 (m*n) 的二维数组很好地完成了工作，其中输入字符串的大小为 m 和 n。

我面临的问题是如果 m 和 n 的值变大，比如说超过 16,000，由于 m*n 数组的大小很大，我会遇到 OutOfMemory 异常。我也遇到了内存碎片和 LargeObjectHeap 问题

问题寻找一个 C# 代码来解决 2 个非常大的字符串（每个包含超过 20k 个单词）的编辑距离问题，而不会出现 OutOfMemory 异常。

MapReduce 或DataBase 或MemoryMappedFile 相关的解决方案不可行。只有纯 C# 代码才能工作。

我有一个包含 10 个字符串的文件 - 每个字符串在 1 行中 - 我需要运行 LCS 并获取每个比较的 LCS 和 LCS 长度，例如，字符串 1 和字符串 2、字符串 1 和字符串 3、字符串 1 和字符串4 依此类推，直到遍历每个字符串，然后递增到字符串 2 并重复此过程，直到遍历所有字符串。

我已成功将每个字符串添加到 ArrayList 以使其更容易，但现在我在尝试将所述字符串相互比较时遇到了麻烦，我想我应该使用嵌套的 for 循环，在它通过之前我不会递增整个列表，然后递增。

任何帮助表示赞赏。这是我到目前为止的代码。

我正在研究关于两个字符串的 LCS 的问题，我想知道从 LCS 的一般情况到其二进制版本是否有任何减少，即通过解决位字符串的 LCS，我们也可以用任意 (但有限）字母基数。

对我来说，存在这样的减少似乎是合理的（基于各种版本问题的算法的复杂性），但是，我找不到类似的东西。

我有n字符串（每个都有自己的大小），字母包含在有限组中 - S（~ 120 个字母）。
我想计算每个字符串到另一个字符串之间的 LCS 结果，并且我希望所有结果都将被标准化。

我想规范化 LCS 结果之间string i并string j避免两个字符串的长度。

示例：
LCS("shpin","shdek")=2因为("[sh]pin","[sh]dek") = "sh"
但是
LCS("shpxaaaaaaaaaan","shaaaaaaaaaadek")=12因为("[sh]px[aaaaaaaaaa]n","[shaaaaaaaaaa]dek") = "shaaaaaaaaaa"

我正在考虑将每个结果除以，Expected Value但我不知道如何计算EV。
有没有人有办法解决吗？也许是另一种获得足够好的近似值的方法？:(

谢谢

我想问一下“ionic run android -lcs”中的标志“lcs”是什么意思？（我对 ionic 框架有一个错误，即我的应用程序仅在使用此标志时以正确的方式构建，但我不知道它们代表什么。）

这两个字符串 {xaybadfeg, abcdefg} 的最长公共子序列是什么。不是“abdeg”吗？我正在使用这个算法（动态编程技术）来寻找解决方案。它返回“adeg”作为答案。我对子序列的理解是错误的吗？我的算法错了吗？我错过了什么吗？我应该为这种类型的输入提供特殊情况吗？

动态编程代码

非常感谢任何输入。谢谢！

当我运行 LCS('human', 'chimp') 时，我得到的是“h”而不是“hm”。当我运行 LCS('gattaca', 'tacgaacta') 时，我得到的是“g”而不是“gaaca”。当我运行 LCS('wow', 'whew') 时，我得到的是正确的“ww”。当我运行 LCS('', 'whew') 时，我得到的是正确的 ""。当我运行 LCS('abcdefgh', 'efghabcd') 时，我得到的是“a”而不是“abcd”。我做错了什么？

这是我的代码：

例子：

{54、87、23、87、45、67、7、85、65、65、3、4、55、76、65、64、5、6、4、54、45、6、4 } ；

{ 76, 57, 65, 3, 4, 55, 76, 65, 64, 5, 6, 4, 54, 45 , 8, 65, 66, 57, 6, 7, 7, 56, 6, 7, 44 , 57, 8, 76, 54, 67 };

基本上，我有两个字节 []，并且需要在两者中找到最大的相同字节序列。

我已经尝试了显而易见的事情并编写了一些代码来暴力破解结果：

但是，在我的应用程序中，字节数组会大得多，甚至达到 GB。所以基本上我需要一个关于如何提高效率的提示/代码。

我正在尝试执行一个 LCS 函数，该函数利用递归来给我 LCS 有效的位置数，以及此处描述的 LCS 的位置：

每当我尝试执行它时，它都会告诉我存在递归错误，如下所示：

我的代码有什么问题？我试图通过递归替换LCS没有应用的区域，但是函数在哪里超出了它的深度？