Content deleted Content added
Line 55:
else:
f[j-k] = i+1
return k
</source>
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.
| |||