我正在尝试实现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 会在这里吗？只是两个阵列上的联合？
阅读并研究了这篇论文后，我可以说这C应该是一个包含字符串字母的数组，其中字母大小（以及 的大小C）为l.
但是，从您的问题来看，我觉得有必要对此进行更深入的研究，因为看起来您还没有了解全部情况。什么是 P[i,j]，为什么需要它？答案是您并不真正需要它，但它是一种优雅的优化。在第 3 页，在定理 1之前一点，据说：
[...] 当第 k 步的 jk = 0 或第 k 步的 a(i) = b(jk) 时，此过程结束。假设该过程在第 k 步停止，并且 k 必须是使 a(i) = b(jk) 或 jk = 0 的最小数。 [...]
(3) 中的递推关系等价于 (2)，但根本区别在于 (2) 递归扩展，而对于 (3)，只要您知道 k ，您就永远不会有递归调用。换句话说，(3) 不递归扩展背后的魔力在于您以某种方式知道 (2) 上的递归将停止的位置，因此您立即查看该单元格，而不是递归地接近它。
好吧，但是你如何找出 的价值k？由于k是 (2) 到达基本情况的位置，因此可以看出这k是您必须“返回”的列数，B直到您超出限制（即，第一列填充 0 )或者B您在字符 in和字符 in之间找到匹配项A（对应于 (2) 中的基本情况条件）。请记住，您将匹配字符a(i-1)，i当前行在哪里。
所以，你真正想要的是找到角色出现B之前的最后一个位置。如果之前没有出现过这样的字符，那么这将等同于达到（2）中的情况；否则，与（2）中的到达相同。ja(i-1)Bji = 0 or j-1 = 0a(i) = b(j-1)
让我们看一个例子：
考虑到算法正在计算 i = 2 和 j = 3 的值（行和列以灰色突出显示）。想象一下，算法正在处理以黑色突出显示的单元格，并且正在应用 (2) 来确定（黑色单元S[2,2]左侧的位置）的值。通过应用 (2)，它将首先查看a(2)和b(2)。a(2)是 C，b(2)是 G，没有匹配（这与原始的著名算法相同）。该算法现在想要找到 的值S[2,2]，因为它需要计算S[2,3]（我们在哪里）。S[2,2]尚不清楚，但该论文表明，无需参考带有 的行即可确定该值i = 2。在（2）中，选择第三种情况：S[2,2] = max(S[1, 2], S[2, 1]). 请注意，如果您愿意的话，这个公式所做的只是查看将用于计算的位置S[2,2]。所以，换个说法：我们正在计算S[2,3]，我们需要S[2,2]它，我们还不知道，所以我们回到桌面上，S[2,2]以几乎与我们在原版中所做的相同的方式查看价值是多少，非并行算法。
这什么时候会停止？在此示例中，当我们在第二个（当前列上的字母）之前找到字母C（这是我们的 ）或到达第 0 列时，它将停止。因为没有before ，所以我们到达第 0 列。另一个示例：a(i)TGTTCGACATCT
在这里，(2) 将在 = 5 处停止j-1，因为这是显示的最后一个TGTTCGACA位置C。因此，递归在 时达到基本a(i) = b(j-1)情况j-1 = 5。
考虑到这一点，我们可以在这里看到一条捷径：如果您能以某种方式知道作为（2）中基本情况的数量k，j-1-k那么您就不必通过分数表来查找基本情况。
这就是背后的全部想法P[i,j]。P是一张表格，您可以在其中垂直放置整个字母表（在左侧）；B再次将绳子水平放置在上侧。该表是作为预处理步骤的一部分计算的，它会准确地告诉您您需要提前知道的内容：对于 中的每个位置j，B它说对于（字母表）中的每个字符C[i]，在C中的最后一个位置是什么B在找到jwhere之前C[i]（请注意，i它用于索引C，字母表，而不是字符串A。也许作者应该使用另一个索引变量以避免混淆）。
因此，您可以将条目的语义P[i,j]视为以下内容：B 中我在位置 j 之前看到 C[i] 的最后一个位置。例如，如果您的字母表是sigma = {A, E, I, O, U}，而B = "AOOIUEI", thenP` 是：
花点时间了解这张表。注意 的行O。请记住：这一行列出了 中的每个位置B，最后一个已知的“O”在哪里。只有在什么时候j = 3我们才会有一个不为零的值（它是 2），因为那是第一个Oin之后的位置AOOIUEI。这个条目说，之前看到的最后一个位置B是O位置 2（实际上，B[2]是一个O，后面的那个A）。请注意，在同一行中， forj = 4的值为 3，因为现在 for 的最后一个位置O是对应于第二个Oin 的位置B（并且由于不再O存在 '，因此该行的其余部分将为 3）。
P回想一下，如果您想轻松找到k使等式（2）中的递归停止的值，则构建是必要的预处理步骤。现在应该P[i,j]是k你在（3）中寻找的。使用P，您可以及时确定该值O(1)。
因此，C[i]in (6) 是字母表中的一个字母——我们目前正在考虑的字母。在上面的示例中，C = [A,E,I,O,U]，C[1] = A，C[2] = E， 等。在等式 (7) 中，c是（正在考虑的字符串的当前字母）C所在的位置。这是有道理的：毕竟，在构建分数表位置时，我们想用- 我们想知道我们最后一次看到in之前的值是在哪里。我们通过阅读来做到这一点。a(i)AS[i,j]Pka(i)BjP[index_of(a(i)), j]
好的，既然您了解了 的用法P，那么让我们看看您的实现发生了什么。
关于您的具体情况
在论文中，P显示为列出整个字母表的表格。遍历字母表是一个好主意，因为该算法的典型用途是在生物信息学中，其中字母表比字符串小得多A，这使得遍历字母表的成本更低。
因为您的字符串是对象序列，所以您C将是所有可能对象的集合，因此您必须P使用所有可能对象实例的集合构建一个表（当然是废话）。与您的字符串大小相比，这绝对是字母大小很大的情况。但是，请注意，您只会在与 from 中的P字母相对应的那些行中建立索引：对于不在其中的字母的A任何行都是无用的，并且永远不会被使用。这使您的生活更轻松，因为这意味着您可以使用字符串而不是使用每个可能对象的字母来构建。PC[i]APA
再举一个例子：如果你的字母表是AEIOU, AisEEI和Bis AOOIUEI，你只会在andP的行中建立索引，所以这就是你所需要的：EIP
这有效且足够，因为在 (7) 中，是字符P[c,j]的入口，并且是 的索引。换句话说：总是属于，因此对于 的大小远小于 的大小的情况，为字符构建而不是使用整个字母表是非常有意义的。Pcca(i)C[c]APAAC
您现在所要做的就是将相同的原则应用于您的任何对象。
我真的不知道如何更好地解释它。起初这可能有点密集。确保重新阅读它，直到你真正理解它——我的意思是每一个小细节。在考虑实施它之前，您必须掌握这一点。
注意：您说您正在寻找可靠和/或官方的消息来源。我只是另一个CS学生，所以我不是官方消息来源，但我认为我可以被认为是“可信的”。我以前研究过这个，我知道这个主题。快乐编码！