c++ - 两个给定字符串的父字符串

Question

给定 2 个字符串，我们必须找到一个长度最小的字符串，使得给定的字符串是该字符串的子序列。换句话说，我们需要找到一个字符串，以便删除一些字符会产生给定的字符串。一直在想蛮力和LCS，但徒劳无功。

12345 和 11234 应该导致 112345 WWA 和 WWS 有一个答案 WWAS

LCS 的内存效率非常低（DP 之一），蛮力只是幼稚。我应该怎么办？

Answer 1

标准库中有一个定义明确的算法可以满足您的目的。

set_union ();

条件是您的输入范围必须排序。

Answer 2

也许您可以使用Needleman-Wunsch和高错配惩罚进行全局对齐，以更喜欢 indels。最后，通过从匹配位置获取字母，然后从任一插入的字母中获取字母，将对齐方式合并为“父字符串”，例如：

WW-A
||  
WWS-

WWSA

或者：

-12345
 ||||
11234-

112345

内存是O(nm)，但修改后缩小到O(min(n,m))。