Lexicographically minimal string rotation

<p>In <a href="/facts/Computer_science/lN3pEyPz">computer science</a>, the lexicographically minimal string rotation or lexicographically least circular substring is the problem of finding the <a href="/facts/String_(computer_science)/4ChJu5WS">rotation of a string</a> possessing the lowest <a href="/facts/Lexicographical_order/xQANy8Br">lexicographical order</a> 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 <a href="/facts/Text_normalization/H56wc4GH">normalizing</a> strings. If the strings represent potentially <a href="/facts/Isomorphism/pj8KgkxU">isomorphic</a> structures such as <a href="/facts/Graph_(discrete_mathematics)/kw3eIBUe">graphs</a>, normalizing in this way allows for simple equality checking.
A common implementation trick when dealing with circular strings is to concatenate the string to itself instead of having to perform <a href="/facts/Modular_arithmetic/0wtRa5dU">modular arithmetic</a> on the string indices.
</p>

Lexicographically minimal string rotation open-in-new

Lexicographically minimal string rotation