我正试图想出一个有效的算法，可以在 JavaScript 中为 longest common subsequence problem 工作.但是，我的问题与维基百科文章中描述的问题有两个主要区别。首先是我会有两组以上的 Angular 色。第二个是 Angular 色永远不会在一组中重复。这意味着每组的长度最多为 50 个字符(即可打印的 ASCII 字符)。
例如，集合可能包含:
A = ZBANICOT
B = ACNTBZIO
C = ANICOTZB
D = ZIANCOTB
... 它应该输出 ACO、ACT、ANO 和 ANT，因为它们是所有 4 个集合中最长的子序列(据我手动检查这些集合所知)。
由于没有一个字母重复，是否有比维基百科文章中描述的算法更有效的算法我应该考虑？如果不是，是否有任何地方描述了如何将算法转换为具有 N 个集合而不是 2 个集合？
最佳答案
不确定正常 LCS 算法的适应效率如何，因此这可能效率低下，但由于符合条件的字母不多，所以它并不太糟糕。
制作一个后继矩阵。对于每个字符串 s , 对于每对字母 (s[i],s[j])与 i < j , 递增 matrix[s[i]][s[j]] .如果matrix[a][b] = n = number of strings，一对字母只能是最长公共(public)子序列的一部分.从参与这种对的字母构建有向图，边来自 a至 b比较 matrix[a][b] = n .在该图中找到最长的路径。
关于javascript - 在可变数量的集合中寻找没有重复字符的最长公共(public)子序列？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/8685598/