Content deleted Content added
m →Booth's Algorithm: added missing apostrophe for markup |
→Booth's Algorithm: Fixed critical bug in Booth algorithm as presented in the original paper |
||
Line 42:
n = len(S)
for j in range(1, 2*n):
i = f[j-k-1]▼
if j-k >= n: # Least circular shift found
if S[j%n] <= S[(k+i+1)%n] and i != -1: # Error correction
k = j-i-1
return k
▲ i = f[j-k-1]
while S[j%n] != S[(k+i+1)%n] and i != -1:
if S[j%n] < S[(k+i+1)%n]:
Line 56 ⟶ 58:
f[j-k] = i+1
</source>
Of interest is that removing all lines of code which modify the value of '''''k''''' results in the original Knuth-Morris-Pratt preprocessing function, as '''''k''''' (representing the rotation) will remain zero. The algorithm presented in the original paper contained a critical bug whereby a candidate rotation with a suffix matching its prefix would be reported as the lexicographically minimal rotation; the line in the above implementation commented "Error correction" fixes this. Booth's algorithm runs in '''''O(n)''''' time, where '''''n''''' is the length of the string. The algorithm performs at most '''''3n''''' comparisons in the worst case, and requires auxiliary memory of length '''''n''''' to hold the failure function table.
===Shiloach's Fast Canonization Algorithm===
| |||