我已经给了N个条件。我必须找到一个字符串s，这样，给定n个字符串是s的子序列。
例如，我给出了以下5个字符串：
AATT
CGTT
CAGT
ACGT
ATGC
然后字符串是“ACAGTGCT”。因为，acagtgct包含所有给定字符串作为超级序列。
要解决这个问题，我必须知道算法但我不知道怎么解决。伙计们，你们能告诉我解决这个问题的方法吗？
最佳答案
这是一个称为多序列比对的np完全问题。
wiki page描述了解决方案方法，例如动态编程，它适用于小n，但对于大n则变得昂贵得令人望而却步。
基本思想是构造一个数组f[a，b，c，…]表示生成第一个字符串的“a”字符、第二个字符串的“b”字符和第三个字符串的“c”字符的最短字符串的长度。