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 rotations of B. We show that this distance may be computed in O(k^2).
|Translated title of the contribution||Necklace Swap Problem for Rhythmic Similarity Measures|
|Title of host publication||Unknown|
|Pages||234 - 245|
|Number of pages||11|
|Publication status||Published - Nov 2005|
Bibliographical noteConference Proceedings/Title of Journal: Proceedings of the 12th International Symposium on String Processing and Information Retrieval (SPIRE '05)
Clifford, R., Mohamed, M., & Pinzon, Y. (2005). Necklace Swap Problem for Rhythmic Similarity Measures. In Unknown (pp. 234 - 245). Springer Verlag. http://www.cs.bris.ac.uk/Publications/pub_info.jsp?id=2000454