algorithm - 将有序事件序列合并到表中

Question

我正在寻找一种算法来解决以下问题:假设我有一个有序事件序列的集合并想从中创建表

AB
BC

导致表格的形式

ABC
**
 **

第一行是标题。对于每个输入序列，我希望在发生的事件的列中有一行带有标记。

另一个更复杂的示例(具有三个序列)是:

AAB
BBA
CBA

导致

CBBAAB
   ***
 ***  
** *

我知道有时有多种可能的解决方案(例如，两个序列只包含一个事件的简单示例，我可以自由决定哪个先出现)。我只对任何解决方案感兴趣，生成的 header 序列(上一个示例中的 CBBAAB)应尽可能短。

有人知道解决该问题的算法吗？

Answer 1

我相信可以用更简单的方法解决这个问题。对我来说，问题似乎是首先找到最短的公共(public)超序列，然后找到标记 - 用超序列计算每个字符串的公共(public)子序列。

例如:

AAB

BBA

CBA

AAB, BBA 之间的最短公共(public)超序列是 BBAAB 或 AABBA那么 BBAAB 和 CBA 之间的最短超序列是 CBBAAB 或者 AABBA 和 CBA 之间是CAABBA

现在要查找AAB 的标记，找到CBBAAB 和AAB 之间的公共(public)子序列。同样适用于 BBA 和 CBBAAB 以及 CBA、CBBAAB

这里有一些链接可以帮助您找到它们:

Shortest common supersequence

Longest common subsequence