string - 来自一袋字符串的超序列

Question

给定一个字符串 s，从一袋字符串中识别 s 的最短超序列的最有效方法是什么？此外，s 的最后一个字符应与超字符串的最后一个字符匹配。

Answer 1

如果不是我理解错了，这个问题肯定是在P中。

一个天真的方法是:

1. 取 B 中所有以与 s 相同的字符结尾的字符串。将这个新包称为 B'。可以在 O(|B|) 中完成
2. 选择包 B' 中所有作为 s 超序列的字符串。 对于 B 中的 z，它可以在 O(|B'|* max(|z|)) 中完成。测试给定字符串 s 是否是另一个字符串 z 的子序列可以在 O(|z|) 中完成
3. 选择先前找到的最短字符串(在 O(|B'|) 中)

在哪里|x|表示 x 的大小。

您可以组合这些步骤，但无论如何都是 O(|B| * max(|z|))。