NECKLACE SWAP PROBLEM FOR RHYTHMIC SIMILARITY MEASURES
Yoán José Pinzón Ardila, Raphaël Clifford, Costas S. Iliopoulos, Gad M. Landau, Manal Mohamed · International Journal of Computational Methods · 2008
Given two n-bit (cyclic) binary strings, A and B, represented on a circle (necklace instances), let each sequence have the same number (k) of 1's. We are interested in computing the cyclic swap distance between A and B, i.e. the minimum number of swaps needed to convert A to B, minimized over all possible rotations of B. We show that, given the compressed representation of A and B, this distance may be computed in O(k2).