algorithm - 两个圆形列表之间的最小编辑距离？

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

只是一个提示，应该考虑更多细节