问题标签 [lcs]

我正在使用 openMP编写最长公共子序列算法的并行版本。

顺序版本如下（并且可以正常工作）：

关键部分是填充分数矩阵，这是我试图主要并行化的部分。

一种方法（我选择）是：用反对角线填充矩阵，所以左上角和左上角的依赖总是得到满足。简而言之，我跟踪对角线（第三个循环，下面的变量i），线程并行填充该对角线。为此，我编写了以下代码：

前两个循环（第一行和第一列）正常工作，线程以平衡的方式填充单元格。

当谈到填充矩阵（对角线）时，没有什么效果很好。我试图调试它，但似乎线程随机地行动和写东西。

我不知道出了什么问题，因为在前两个循环中根本没有问题。

任何想法？

PS我知道以对角线方式访问矩阵对缓存非常不友好，线程可能不平衡，但我现在只需要它工作。

PS #2 我不知道它是否有用，但我的 CPU 最多有 8 个线程。

我编写了以下代码C#来获取使用给定的两个文本的最长公共子序列的长度，但它不适用于大字符串。请你帮助我好吗。我真的很困惑。

我知道如何找到两个序列/字符串的 lcs，但 lcs 并没有限制子序列必须是连续的。我已经尝试如下

wherelongest_string返回数组中最长的字符串，s[1:]表示从第一个字符开始的 s 切片。

我已经在 javascript 中的浏览器和 golang 中运行它，在远程服务器上，我将每个对 lccs 的调用放在它自己的 goroutine 中，虽然我不知道服务器的硬件规格，所以我不知道这些例程的并行化。

在这两种情况下，对于我的需求来说，运行速度都太慢了。有没有办法加快这个速度？

我想打印 LCS 问题的所有可能解决方案。

两个字符串 abcbdab 和 bdcaba 应该打印以下 3 个字符串：bdab,bcba,bcab。

C是根据算法取值的全局矩阵表，m，n是序列a，b的长度。

但是输出是出乎意料的。

我曾经根据我的需要使用动态编程O(m * n)、后缀树O(m + n)、后缀数组O(nlog^2 n)来计算最长公共子串。最近我学习了Suffix Automaton，它在O(n)中的表现非常令人印象深刻。

我可以编写可以轻松计算最长公共子串长度的代码。例如：

这是代码：

但现在我需要打印最长的公共子字符串本身，而不是长度。但是我无法修改我的代码:(如何修改此代码以打印最长的公共子字符串？

给定一个数组，我们需要找到可以使它不递减的最小步数。我们可以选择 i & j 并在每个步骤中为区间 a[i] 到 a[j]（包括两者）中的所有元素添加 '1'

我认为它可以使用 DP 解决，但想不到它......请帮助

我在编程比赛中遇到了这个问题，我认为它可以由 DP 解决，但想不出任何问题，所以请帮忙。这是任务：

有 n 摞硬币线性放置，每摞从 1 到 n 标记。你还有一袋硬币，里面装着无限的硬币。堆栈和麻袋中的所有硬币都是相同的。您所要做的就是使硬币的高度不降低。

您选择两个堆栈 i 和 j 并在从堆栈'i'到堆栈'j'（包括）的每一堆硬币上放置一枚硬币。这个完整的操作被认为是一个动作。您必须尽量减少移动次数以使高度不降低。

输入规范： 会有一些测试用例。读到EOF。每个测试用例的第一行将包含一个整数 n，第二行包含 n 个高度 (h[i]) 的堆栈。

输出规范： 输出单个整数，表示每个测试用例的移动次数。

我正在尝试实现http://www.iaeng.org/publication/WCE2010/WCE2010_pp499-504.pdf中描述的最长公共子序列问题的并行算法

但是我在第 4 页的公式 6 中的变量 C 有问题

该论文在第 3 页末尾将 C 称为

C as Let C[1 : l] 是有限字母表

我不确定这是什么意思，因为我猜它会与 2 个字符串ABCDEF和ABQXYEFbe 一起使用ABCDEFQXY。但是，如果我的 2 个 stings 是一个对象列表（例如，我的匹配测试在哪里obj1.Name = obj2.Name），我的 C 会在这里吗？只是两个阵列上的联合？

我正在使用递归方法在 php 程序中编码 LCS（最长公共子序列）。我有以下代码：

要打印 LCS，我调用以下函数：

此代码正确计算 LCS 的总长度，但在 print 函数中每次调用此行时都会给出“注意：未定义的偏移量：-1”echo $x[$i-1];并且什么也不打印。我已经尝试了几乎所有方法来拆分 $str1 的字符串，然后将其传递给函数，但没有任何效果。它不打印 LCS 字符串，因为这行代码有问题echo $x[$i-1];，我无法得到。请帮忙。

注意：上述代码的伪代码取自 Thomas H. Cormen 的书“Introduction to Algorithms 3rd Edition”。我正在将它写入 PHP 以扩展它，以便它可以打印两个以上字符串的 LCS。如果有人分享我如何扩展此代码的想法，以便它可以打印具有多个字符串（如 $array{'sdsad'、'asddaw'、'asd'、...n} ）的数组的 LCS，我将不胜感激。后来打算把整个程序转成MATLAB。

的复发lcs是：

你能告诉我为什么会这样吗i-1？j-1为什么不L[i,j] = L[i-1,j-1]正确？