string - 将字符串a转换为字符串b

Question

给定 2 个字符串 A 和 B，您必须通过两个操作将 A 转换为 B:

• delete(i, len):从A中删除从i开始的len个字符(可以不删除任何字符)
• insert(i, str):在A中第i索引处插入字符串str(可以插入空字符串)

您必须尽量减少删除操作删除的字符数。

约束:

• insert只能在delete之后应用
• 删除和插入只能应用一次

示例 1:

A = aabcdef  
B = aaefg

答案:delete(2, 3); 插入(4，“g”)。总而言之，我们最多只能删除 3 个字符。

例子2:

A = aaaaa  
B = a

我们只需要删除4个字符

我想到了O(n^3) 和O(n^2) 解决方案，但有人告诉我有比这更好的解决方案。

Answer 1

我想我得到了一个 O(n)解决方案。它分几个步骤完成。

首先，让我们重新表述问题。我们必须从 A 中删除一个子字符串和来自 B 的子串这样剩下的就相等了。我们想从 A 中删除短子串尽可能。请注意，您的插入操作实际上等同于 B 上的相同删除操作。 .

引理。如果您从 A 中去掉相同的前缀或后缀和 B ，不会影响最优解。把证据留给读者:)

现在，提取A的最大公共(public)后缀和前缀和 B , 所以 A=XA*Y , B=XB*Y , 其中X和 Y是子串。如果A*或 B*是空的，我们得到一个简单的退化案例。如果不是，让我们做一个新的符号A<-A* , B<-B* .

此时first(A) != first(B)和 last(A) != last(B) .否则，我们应该在前面的步骤中包含一个公共(public)符号作为前缀或后缀:

A = a1 A' a2
B = b1 B' b2

哪里a1 = first(A) , a2 = last(A) , b1 = first(B) , b2 = last(B)和 A'和 B'是 A 的子串和 B .这里a1 != b1 , a2 != b2 .

制作A和 B equal 我们必须从一个字符串中删除第一个符号，从另一个字符串中删除最后一个符号。你这里有两个案例。让我们只考虑一个，您从 A 中删除第一个符号最后一个符号来自 B .

您现在要做的就是从 A 的开头删除 as less 符号尽可能，以便留下的后缀等于 B 的某个前缀.为此，你应该构造一个 suffix tree字符串 A并遍历 B 的所有前缀检查它们是否出现在后缀树中。然后选择最大的。完成后，您将拥有最大的字符串 C , 这是 A 的后缀和 B 的前缀:

A = PC
B = CS

删除 P来自 A和 S来自 B大功告成。

求原文A和 B (没有删除公共(public)部分)我们有:

A = XPCY
B = XCSY

在问题的原始表述中，P被删除并且S被插入。

可以在O(n)中构建后缀树.在第一步剥离最常见的后缀和前缀需要 O(n) .后缀树遍历在O(n)中完成.