Content deleted Content added
Booth's algorithm was wrong (tested it in my own code), so I replaced it with a correct version, including the fix from Booth himself https://www.cs.ubc.ca/~ksbooth/PUB/LCS.shtml |
→Booth's Algorithm: add docstring |
||
Line 37:
<syntaxhighlight lang="python">
def least_rotation(
"""Booth's lexicographically minimal string rotation algorithm."""
n = len(
f = [-1] * (2 * n)
k = 0
for j in range(1, 2 * n):
i = f[j - k - 1]
while i != -1 and
if
k = j - i - 1
i = f[i]
if i == -1 and
if
k = j
f[j - k] = -1
| |||