1

给定 2 个字符串A和，您必须在两个操作B中转换A为：B

  • delete(i, len)i: 删除从from开始的 len 个字符A（你可以不删除任何字符）
  • insert(i, str)A:在-th 索引处插入一个字符串 str i（你可以插入一个空字符串）

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

约束：

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

示例 1：

A = aabcdef  
B = aaefg

答案：delete(2, 3); insert(4, "g"). 总而言之，删除了 3 个字符，这是我们能做的最好的。

示例 2：

A = aaaaa  
B = a

我们只需要删除 4 个字符

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

4

1 回答 1

2

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

首先，让我们重新表述问题。我们必须从中删除一个子字符串A和一个子字符串，B以便剩下的内容相等。我们想从Aas possbile 中删除 as short substring。请注意，您的插入操作实际上等同于对B.

引理。如果从Aand中去掉相等的前缀或后缀B，则不会影响最佳解决方案。把证据留给读者:)

现在，提取 and 的最大公共后缀和前缀A，Bso A=XA*Y, B=XB*Y, where Xand Yare substrings。如果A*orB*为空，我们得到一个简单的退化案例。如果不是，让我们做一个新的符号A<-A*，B<-B*。

此时first(A) != first(B)和last(A) != last(B)。否则，我们应该在上一步中包含一个通用符号作为前缀或后缀：

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

其中a1 = first(A), a2 = last(A), b1 = first(B), b2 = last(B)and是A'and的子B'串。在这里，。ABa1 != b1a2 != b2

为了使相等A，B我们必须从一个字符串中删除第一个符号并从另一个字符串中删除最后一个符号。你这里有两个案例。让我们只考虑一个，您从 中删除第一个符号和从 中删除A最后一个符号B。

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

A = PC
B = CS

P从A和S从删除B，你就完成了。

对于原始A和B（未删除公共部分），我们有：

A = XPCY
B = XCSY

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

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

于 2013-04-01T07:40:26.080 回答