algorithm - 2 つの循環リスト間の編集距離は最小ですか?

Question

2 つの循環リストが与えられた場合、2 つのリスト間の最適な配置を計算する効率的な方法はありますか? たとえば、循環リストが与えられた場合:

a b b c
b c a

最適なアライメントは

a b b c
a b _ c

この配置は編集距離が最も小さいためです (注: この最適な配置は一意ではなく、一意である必要もありません)。

これを行う 1 つの方法は、最初のリストと 2 番目のリストの各巡回順列の間の編集距離を計算し、最小編集距離を最適な位置合わせとして使用することです。そうするためのより効率的な方法はありますか？

Answer 1

S1="abbc"、S2="bca" とします。

ここで、S2'=strcat(S2,S2)="bcabca" とし、S1 と S2' の間の編集距離を計算すると、次のようになります。

--abbc-
bcab-ca

単なるヒントです。詳細を検討する必要があります