Complexité de la distance de modification du bloc avec l'échange uniquement

Question

Supposons que j'ai distinct Lettres dans un alphabet $ sum = {a_1, a_2, ..., a_n } $. J'ai également deux permutations de ces lettres, appelons-les $ a, b $. Comment puis-je trouver la distance de modification entre $ a $ et $ b $ avec les opérations d'édition de bloc autorisées?

Pour le rendre plus clair, un exemple serait $ sum = {a, b, c, d } $. Deux permutations possibles sont $ a = `` abcd ", b =` `dabc" $. La distance d'édition ici serait de 1 $ car nous pouvons échanger le bloc $ `` ABC "$ avec $` `d" $ pour obtenir une chaîne à l'autre.

De toute évidence, il n'y aura pas de suppressions / insertions dans cette forme du problème, ce sera purement des échanges car les deux chaînes sont des permutations des mêmes lettres.

Maintenant, je sais que le problème d'origine du bloc d'édition avec toutes les opérations est du NP-dur, cependant, la restriction de seuls échanges de blocage rendrait-elle peut-être cette résolution en temps polynomial? La plupart des textes que j'ai lus ne traitent pas de cette version et traitent plutôt des variations du problème d'origine. Toute aide serait appréciée.