Content deleted Content added
m v2.05b - Bot T20 CW#61 - Fix errors for CW project (Reference before punctuation) |
MOS:HEAD |
||
Line 21:
==Algorithms==
===The
The naive algorithm for finding the lexicographically minimal rotation of a string is to iterate through successive rotations while keeping track of the most lexicographically minimal rotation encountered. If the string is of length {{mvar|n}}, this algorithm runs in {{math|''O''(''n''<sup>2</sup>)}} time in the worst case.
===Booth's
An efficient algorithm was proposed by Booth (1980).<ref>{{cite journal
| author = Kellogg S. Booth
Line 62:
Of interest is that removing all lines of code which modify the value of {{mvar|k}} results in the original Knuth-Morris-Pratt preprocessing function, as {{mvar|k}} (representing the rotation) will remain zero. Booth's algorithm runs in {{tmath|O(n)}} time, where {{mvar|n}} is the length of the string. The algorithm performs at most {{tmath|3n}} comparisons in the worst case, and requires auxiliary memory of length {{mvar|n}} to hold the failure function table.
===Shiloach's
Shiloach (1981)<ref>{{cite journal
| title = Fast canonization of circular strings
Line 79:
The algorithm is divided into two phases. The first phase is a quick sieve which rules out indices that are obviously not starting locations for the lexicographically minimal rotation. The second phase then finds the lexicographically minimal rotation start index from the indices which remain.
===Duval's Lyndon
Duval (1983)<ref>{{cite journal
| title = Factorizing words over an ordered alphabet
Line 109:
proposed an algorithm to efficiently compare two circular strings for equality without a normalization requirement. An additional application which arises from the algorithm is the fast generation of certain chemical structures without repetitions.
A variant for [[
| author = Wang, Q., Ying, M.
| title = Quantum Algorithm for Lexicographically Minimal String Rotation
| |||