Content deleted Content added
→Booth's Algorithm: format code (with Blackened) |
change source to syntaxhighlight |
||
Line 36:
The algorithm uses a modified preprocessing function from the [[Knuth-Morris-Pratt algorithm|Knuth-Morris-Pratt string search algorithm]]. The failure function for the string is computed as normal, but the string is rotated during the computation so some indices must be computed more than once as they wrap around. Once all indices of the failure function have been successfully computed without the string rotating again, the minimal lexicographical rotation is known to be found and its starting index is returned. The correctness of the algorithm is somewhat difficult to understand, but it is easy to implement.
<
def least_rotation(S: str) -> int:
"""Booth's algorithm."""
Line 56:
f[j - k] = i + 1
return k
</syntaxhighlight>
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.
| |||