Lexicographically minimal string rotation: Difference between revisions

Revision as of 03:26, 19 April 2012

Revision as of 21:37, 20 July 2012

Line 1:

In [[computer science]], the '''lexicographically minimal string rotation''' or '''lexicographically least circular substring''' is the problem of finding the rotation of a [[String (computer science)|string]] possessing the lowest [[Lexicographical order|lexicographical order]] of all such rotations. For example, the lexicographically minimal rotation of "bbaaccaadd" would be "aaccaaddbb". It is possible for a string to have multiple lexicographically minimal rotations, but for most applications this does not matter as the rotations must be equivalent. Finding the lexicographically minimal rotation is useful as a way of [[Text normalization|normalizing]] strings. If the strings represent potentially [[Isomorphism|isomorphic]] structures such as [[Graph (mathematics)|graphs]], normalizing in this way allows for simple equality checking.<ref>{{cite journal

| author = Kellogg S. Booth

| last2 = Colbourn | first2 = Charles J.

Line 14:

| issn = 0097-5397 }}

</ref>

A common implementation trick when dealing with circular strings is to concatenate the string to itself instead of having to perform [[Modular arithmetic|modular arithmetic]] on the string indices.

==Algorithms==