Lexicographically minimal string rotation: Difference between revisions

Revision as of 17:17, 9 April 2012

Revision as of 17:18, 9 April 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

| last1 = Booth | first1author = Kellogg S. Booth

| last2 = Colbourn | first2 = Charles J.

| author2-link = Charles Colbourn

| title = Linear Time Automorphism Algorithms for Trees, Interval Graphs, and Planar Graphs

| Journaljournal = SIAM Journal on Computing

| Publisherpublisher = Society for Industrial and Applied Mathematics

| volume = 10

| issue = 1