我有一个问题，我需要一个算法来解决它。
我找不到它，我不知道问题是否是 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”。我将只需要一个输出，任何输出都是有效的，如果它的长度是可能的最小长度。
感谢
最佳答案
这个问题叫做Shortest Common Supersequence并且已知是 NP 完全的。如果您对近似值没有问题，您可以四处搜索并找到类似这样的东西:An Approximation Algorithm for the Shortest Common Supersequence Problem: An Experimental Analysis, Barone et. al (pdf) .
关于string - 合并符号序列，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/11657870/