合并符号序列

Question

我有一个问题,我需要一个算法来解决它.
我找不到它,我不知道问题是否是NP-Hard.

问题是:我有几个符号序列.我想将它们合并为单个序列,其中包括原始序列的所有符号,保持符号的原始顺序.应删除来自不同序列的重复符号.结果序列必须是可能的最小序列.

如果序列之一是"abc",则得到的序列必须是*a*b*c*,其中*是0或更多符号的序列.如果输入序列是'abc'和'cba',则输出必须是'abcba','c'包含一次,并保留*a*b*c*和*c*b*a*属性.

示例:

输入:

abcde
xbcaf
axdaf

如何合并的方式:

a-bcde--
-xbc--af
ax--d-af

输出:

axbcdeaf

多个输出是可能的,'abcd'和'cba'将导致'abcdba','abcbda'或'abcbad'.我只需要一个输出,任何输出都是有效的,如果它的长度是可能的最小长度.

谢谢

Answer 1

这个问题被称为最短共同序列,并且已知是NP完全的.如果你对近似值没问题,你可以搜索一下这样的事情:最短共同超序问题的近似算法:实验分析,Barone等.al(pdf).