来自一袋琴弦的超级序列

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|)) 。