轉化字符串到串B

Question

鑑於2串A和B，你有兩種操作來變換A到B：

• delete(i, len)：從A刪除i開始len個char（你可以刪除任何字符）
• insert(i, str)：在i個指數中插入一個A字符串str（你可以插入一個空字符串）

您必須最小化刪除操作刪除的字符數。

約束：

• 插入只能應用於刪除後
• 刪除和插入只能一次

例1應用：

A = aabcdef 
B = aaefg 

答：delete(2, 3); insert(4, "g")。總而言之，3個字符被刪除，這是我們能做的最好的。

例2：

A = aaaaa 
B = a 

我們只需要刪除4個字符

我認爲O(n^3)和O(n^2)解決方案，但有人告訴我，有比這更好的解決方案。

Answer 1

我想我得到了一個O(n)解決方案。它分幾步完成。

首先，讓我們重新思考問題。我們必須從A中刪除一個子字符串，並從B中刪除一個子字符串，以便剩下的內容相等。我們想從A中移除短小的子字符串作爲possbile。請注意，您的插入操作實際上等效於B上的相同刪除操作。

引理。如果從A和B中剝去相同的前綴或後綴，則不會影響最佳解決方案。留下證據，讀者:)

現在，提取A和B，所以A=XA*Y，B=XB*Y，其中X和Y子是最大的共同後綴，前綴。如果A*或B*爲空，我們得到了一個簡單的退化情況。如果不是，讓我們做一個新的記號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)和A'和B'是A和B子。這裏a1 != b1,a2 != b2。

要使A和B相等，我們必須從一個字符串中移除第一個符號，並從另一箇中移除最後一個符號。你有兩種情況。讓我們考慮只有一個，您從A中刪除第一個符號，從B中刪除最後一個符號。

現在您只需從A開頭刪除儘可能少的符號，以便後綴將等於B的某個前綴。爲此，您應該構建字符串A的suffix tree並遍歷B的所有前綴以檢查它們是否以後綴樹呈現。然後挑選最大的。一旦你做，你有最大的字符串C，這是A後綴和B前綴：

A = PC 
B = CS 

從A和S從B刪除P就大功告成了。

對於原始A和B（沒有共同的部分移除），我們有：

A = XPCY 
B = XCSY 

在問題的原始製劑，P被刪除並S被插入。

後綴樹可以構建在O(n)。在第一步中刪除最常見的後綴和前綴需要O(n)。後綴樹遍歷在O(n)完成。