问题标签 [lcs]

是否有任何有效的算法来计算两个给定字符串的最长公共回文子序列的长度？

例如：

字符串 1。 afbcdfca

字符串 2。 bcadfcgyfka

LCPS 为 5，LCPS 字符串为afcfa.

我想实现一个执行以下 I/O 的 LCS 版本：

输入：superLCS('cat','car')

输出：['ca#','ca#']

目前，我的程序适用于此，但如果字母不合适，它就不起作用。

例如，如果输入是：superLCS('art','cad')，则输出 ['###','###']。它应该输出 ['a##','#a#']

代码：

我非常接近完成我的程序，但我遇到了一个小问题。I/O 应该是这样的：

但是我的，执行以下操作：

有人可以编辑我的代码，以便我得到正确的答案。我想不通。谢谢：

以下是程序应该返回的更多 I/O：

fanlc2("x", "y")

[0, '#', '#']

fanlc2("垃圾邮件", "")

[0, '####', '']

fanlc2（“水疗中心”，“米”）

[0, "###", "#"]

fanlc2("猫", "汽车")

[2, "ca#, "ca#"]

fanlc2（“猫”，“lca”）

[2, "ca#", "#ca"]

fanlc2（“人类”，“黑猩猩”）

[4, 'h#man', '#h#m#an###']

各位程序员好，

我想就近乎匹配的字符串寻求一些帮助。

目前，我有一个存储描述字符串的程序，用户可以通过完全或部分输入来搜索描述。

我想实现近似匹配搜索。例如，实际描述是“hello world”，但用户错误地输入了搜索“hello eorld”。程序应该能够向用户返回“hello world”。

我尝试查看模式和匹配来实现它，但它需要一个正则表达式来匹配字符串，因此我的描述没有常规模式。我也尝试过 string.contains，但它似乎也不起作用。下面是我尝试实现的部分代码。

其他程序员可以帮我解决这个问题吗？

LCS 的并行计算遵循波前模式。这是比串行实现慢的并行功能。（我认为对角线的数量（平行）与行数（串行）与它有关）

这是串行功能

...以为我会添加测试功能

关于最长公共子序列问题，所有在线资源中介绍的基本算法对我来说都很清楚。此处描述了此算法：

我不清楚的是为算法的动态编程版本提出的算法，它无处不在，如下所示：

但是我看不出DP版本是如何等效的。令我困扰的是，在 DP 版本中，当我们X[i] == Y[j]在内循环中发现时，我们继续计算 DP 相同i；即内部循环的其余部分保持与相同的比较X[i]。既然递归算法说我们应该评估 C[i - 1, j - 1]，我们不应该继续下一个i吗？

我设计了一个算法来找到最长的公共子序列。这些是步骤：

• 选择第一个字符串中的第一个字母。

• 在第二个字符串中查找它，如果找到，将该字母添加到 common_subsequence并将其位置存储在 中index，否则将 的长度common_subsequence与 的长度进行比较lcs ，如果更大，则将其值分配给lcs。

• 返回第一个字符串并选择下一个字母并再次重复上一步，但这一次从第一个index字母开始搜索

• 重复此过程，直到第一个字符串中没有要选择的字母。最后的值lcs是最长公共子序列。

这是一个例子：
</p>

选择A第一个字符串。在 中
寻找。 现在第二个字符串中有一个，将其附加到. 返回到第一个字符串并选择下一个字母. 这次从 的位置开始在第二个字符串中查找。 有一个之后，所以将 B 附加到. 现在选择第一个字符串中的下一个字母. 第二个字符串中没有旁边。所以将 common_subsequence 的值赋值给，因为它的长度大于. 重复前面的步骤，直到到达第一个字符串的末尾。最终的价值AY
Acommon_subsequence
BBA
BAcommon_subsequence
CCBlcslcslcs是最长公共子序列。

该算法的复杂度为 theta(n*m)。这是我的实现：

第一种算法：

使用哈希表的相同算法：

如何在不使用数组且仅列出 ocaml 中的折叠的情况下找到最长的公共子序列

只是一个关于最长公共子序列算法的快速问题。我已经完成了您需要生成子序列的部分，如下所示：

和 printDiff 函数如下：

然后，如果我将其用作参数：

在使用 lcsLength() 生成 opt 矩阵后，我希望 printdiff 能给我：

但相反，我得到：

关于我做错了什么的任何想法都会对我有很大帮助

谢谢洛朗

我有两个字符变量（对象名称），我想提取最大的公共子字符串。

我想要以下结果：

这些向量作为输入应该给出相同的结果：

这些例子具有代表性。字符串包含标识元素，每个向量元素中的其余文本是常见的，但未知的。

是否有解决方案，在以下位置之一（按优先顺序）：

1. 碱基R

2. 推荐套餐

3. CRAN 上可用的软件包

假设重复的答案不满足这些要求。