寻找最长公共子在设定变量量没有重复的字符？ [英] Finding the longest common subsequence in a variable amount of sets with no repeating characters?

问题描述

我试图想出一个有效的算法，将工作在JavaScript的最长的共同序列问题的。不过，也有我的问题，维基百科的文章中描述的之间有两个主要区别。首先是，我将有两个以上的字符集。第二个是，字符永远不会重复的一组。这意味着，每个组的长度将是最多约50个字符（即打印的ASCII字符）。

I'm trying to come up with an efficient algorithm that would work in JavaScript for the longest common subsequence problem. However, there are two main differences between my problem and the one described in the Wikipedia article. The first is that I will have more than two sets of characters. The second is that characters will never repeat in a set. This means that the length of each set will be at most about 50 characters (i.e. the printable ASCII chars).

例如，该套可以包含：

A = ZBANICOT
B = ACNTBZIO
C = ANICOTZB
D = ZIANCOTB

...它应该输出 ACO ， ACT ， ANO 和 ANT ，因为这些是最长的子序列中的所有4台（据我可以告诉手动检查这些套）。

... and it should output ACO, ACT, ANO, and ANT, since these are the longest subsequences in all 4 sets (as far as I can tell from manually examining these sets).

由于没有一个字母的重复，有没有更有效的算法，我应该考虑，而不是维基百科的文章中所描述的？如果没有，是否有任何地方，说明如何将算法转换为具有N台，而不是2？

Since none of the letters repeat, is there a more efficient algorithm I should consider rather than the one described in the Wikipedia article? If not, is there anywhere that describes how to convert the algorithm to having N sets instead of 2?

推荐答案

不知道如何有效地正常LCS算法的适应就可以了，所以这可能是低效的，但因为没有很多符合条件的字母，这不是太太可怕了。

Not sure how efficient an adaption of the normal LCS algorithm would be, so this may be inefficient, but since there aren't many eligible letters, it's not too horrible.

请继任矩阵。对于每一个字符串取值，每对字母（S [I]，S [J]。）与 I＆LT; Ĵ，增量矩阵[S [I] [S [J] 。一对字母只能是一个最长公共子序列的一部分，如果矩阵[A] [B] = N =串号。建立从参与这样一对字母，与边缘有向图中从 A 到 B 当且仅当矩阵[A] [B] = N 。找到该图中的最长路径。

Make a successor matrix. For each string s, for each pair of letters (s[i],s[j]) with i < j, increment matrix[s[i]][s[j]]. A pair of letters can only be part of a longest common subsequence if matrix[a][b] = n = number of strings. Build a directed graph from the letters participating in such a pair, with an edge from a to b iff matrix[a][b] = n. Find a longest path in that graph.

这篇关于寻找最长公共子在设定变量量没有重复的字符？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！