兩個圓形列表之間的最小編輯距離？

Question

給定兩個循環列表，是否有一種計算兩個列表之間最佳對齊的有效方法？例如，給定圓名單：

a b b c 
b c a 

最佳比是

a b b c 
a b _ c 

因爲這對準具有最小編輯距離（注意：這最優比對是不是和不必是唯一的）。

執行此操作的一種方法是計算第一個列表與第二個列表的每個循環置換之間的編輯距離，將最小編輯距離作爲最佳對齊。有沒有更有效的方法來做到這一點？

Answer 1

假設S1 = 「ABBC」，S2 = 「BCA」

現在讓S2 '= strcat的（S2，S2）= 「bcabca」，然後計算S1和S2之間的編輯距離'，你會得到

--abbc- 
bcab-ca 

只是一個提示，更多的細節，應考慮