Lexicographically minimal string rotation: Difference between revisions

Revision as of 14:43, 31 January 2016

Revision as of 20:31, 31 January 2016

Line 1:

In [[computer science]], the '''lexicographically minimal string rotation''' or '''lexicographically least circular substring''' is the problem of finding the [[String_(computer_science)#Rotations|rotation of a string]] possessing the lowest [[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 (discrete mathematics)|graphs]]{{dn|date=January 2016}}, normalizing in this way allows for simple equality checking.<ref>{{cite journal

| author = Kellogg S. Booth

| last2 = Colbourn | first2 = Charles J.